Iterated \(k\)-line graphs (Q1334947)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Iterated \(k\)-line graphs
scientific article

    Statements

    Iterated \(k\)-line graphs (English)
    0 references
    0 references
    0 references
    0 references
    26 September 1994
    0 references
    ``For integers \(k \geq 2\), the \(k\)-line graph of a graph \(G\) is defined as a graph whose vertices correspond to the complete subgraphs on \(k\) vertices in \(G\) with two distinct vertices adjacent if the corresponding complete subgraphs have \(k-1\) common vertices in \(G\).'' Starting with a graph \(G\), one can construct the sequence of graphs in which the next term is the \(k\)-line graph of the previous one. These sequences can by divided into the following three types: (i) the graphs in the sequence vanish after finitely many steps; (ii) the graphs do not vanish and no two of them are isomorphic; (iii) the graphs do not vanish and two graphs are isomorphic. For any fixed \(k \geq 2\) and a chosen type, the authors characterize graphs that produce sequences of the prescribed type.
    0 references
    0 references
    line graph
    0 references