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
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
line graph
0 references