Generalized line graphs: Cartesian products and complexity of recognition
Summary: Putting the concept of line graph in a more general setting, for a positive integer \(k\), the \(k\)-line graph \(L_k(G)\) of a graph \(G\) has the \(K_k\)-subgraphs of \(G\) as its vertices, and two vertices of \(L_k(G)\) are adjacent if the corresponding copies of \(K_k\) in \(G\) share \(k-1\) vertices. Then, 2-line graph is just the line graph in usual sense, whilst 3-line graph is also known as triangle graph. The \(k\)-anti-Gallai graph \(\triangle_k(G)\) of \(G\) is a specified subgraph of \(L_k(G)\) in which two vertices are adjacent if the corresponding two \(K_k\)-subgraphs are contained in a common \(K_{k+1}\)-subgraph in \(G\).{ }We give a unified characterization for nontrivial connected graphs \(G\) and \(F\) such that the Cartesian product \(G\square F\) is a \(k\)-line graph. In particular for \(k=3\), this answers the question of \textit{J. Bagga} [Int. J. Math. Math. Sci. 2004, No. 29--32, 1509--1521 (2004; Zbl 1061.05078)], yielding the necessary and sufficient condition that \(G\) is the line graph of a triangle-free graph and \(F\) is a complete graph (or vice versa). We show that for any \(k\geq 3\), the \(k\)-line graph of a connected graph \(G\) is isomorphic to the line graph of \(G\) if and only if \(G=K_{k+2}\). Furthermore, we prove that the recognition problem of \(k\)-line graphs and that of \(k\)-anti-Gallai graphs are NP-complete for each \(k\geq 3\).
- \(K_ i\)-covers. I: Complexity and polytopes
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- Characterizations of derived graphs
- Convergence of sequences of iterated triangular line graphs
- Gallai and anti-Gallai graphs of a graph
- Gallai graphs and anti-Gallai graphs
- scientific article; zbMATH DE number 851097 (Why is no real title available?)
- Intersection multigraphs of uniform hypergraphs
- Ki-covers. II.Ki-perfect graphs
- Old and new generalizations of line graphs
- On the hardness of recognizing triangular line graphs
- Perfect k‐line graphs and k‐total graphs
- Small edge sets meeting all triangles of a graph
- Transitiv orientierbare Graphen
- Triangular line graphs and word sense disambiguation
- Two characterizations of interchange graphs of complete m-partite graphs
- Gallai graphs and anti-Gallai graphs
- The recognition problem for line bigraphs
- Triangle packings and transversals of some \(K_{4}\)-free graphs
- Induced cycles in triangle graphs
- scientific article; zbMATH DE number 38312 (Why is no real title available?)
- On the hardness of recognizing triangular line graphs
- Perfect k‐line graphs and k‐total graphs
- A survey of the studies on Gallai and anti-Gallai graphs
- EULERIAN AND HAMILTONIAN PROPERTIES OF GALLAI AND ANTI-GALLAI TOTAL GRAPHS
- Recognizing Cartesian products in linear time
This page was built for publication: Generalized line graphs: Cartesian products and complexity of recognition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q888591)
