Generalized line graphs: Cartesian products and complexity of recognition (Q888591)

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\).