Generalized line graphs: Cartesian products and complexity of recognition
type: Item
instance of: scholarly article
title: Generalized line graphs: Cartesian products and complexity of recognition
zbMATH Open document ID: 1323.05109
author: Aparna Lakshmanan S.
author: Csilla Bujtás
author: Zsolt Tuza
published in: The Electronic Journal of Combinatorics
publication date: 2015-11-02T00:00:00Z
full work available at URL: v22i3p33
review text: 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\).
Mathematics Subject Classification ID: 05C76
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6502776
zbMATH Keywords: triangle graph
zbMATH Keywords: \(k\)-line graph
zbMATH Keywords: anti-Gallai graph
zbMATH Keywords: Cartesian product graph
MaRDI profile type: Publication
cites work: Triangular line graphs and word sense disambiguation
cites work: On the hardness of recognizing triangular line graphs
cites work: Small edge sets meeting all triangles of a graph
cites work: Gallai and anti-Gallai graphs of a graph
cites work: Old and new generalizations of line graphs
cites work: Characterizations of derived graphs
cites work: \(K_ i\)-covers. I: Complexity and polytopes
cites work: Ki-covers. II.Ki-perfect graphs
cites work: Two characterizations of interchange graphs of complete m-partite graphs
cites work: Convergence of sequences of iterated triangular line graphs
cites work: Transitiv orientierbare Graphen
cites work: Perfect k‐line graphs and k‐total graphs
cites work: Gallai graphs and anti-Gallai graphs
cites work: An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
cites work: Q4867717
cites work: Intersection multigraphs of uniform hypergraphs
cites work: A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
description: scientific article; zbMATH DE number 6502776