Generalized Line Graphs: Cartesian Products and Complexity of Recognition

  • Aparna Lakshmanan S.
  • Csilla Bujtás
  • Zsolt Tuza
Keywords: Triangle graph, k-line graph, anti-Gallai graph, cartesian product graph


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\Box F$ is a $k$-line graph. In particular for $k=3$, this answers the question of Bagga (2004), 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\ge 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\ge 3$.

Author Biographies

Aparna Lakshmanan S., St. Xavier's College for Women Aluva, Kerala
Department of Mathematics
Csilla Bujtás, University of Pannonia Veszprém
Department of Computer Science and Systems Technology

Zsolt Tuza, Hungarian Academy of Sciences Budapest
Alfréd Rényi Institute of Mathematics
Article Number