Generalized line graphs: Cartesian products and complexity of recognition

Lakshmanan, Aparna S. and Bujtás, Csilla and Tuza, Zsolt (2015) Generalized line graphs: Cartesian products and complexity of recognition. The Electronic Journal of Combinatorics, 22 (3). pp. 1-19. ISSN 1077-8926

Preview

Text 3983_14954_4_PB_u.pdf Download (472kB) | Preview

Abstract

Putting the concept of line graph in a more general setting, for a positive integer k the k-line graph L<inf>k</inf>(G) of a graph G has the Kk-subgraphs of G as its vertices, and two vertices of L<inf>k</inf>(G) are adjacent if the corresponding copies of K<inf>k</inf> 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 Δ<inf>k</inf>(G) of G is a specified subgraph of L<inf>k</inf>(G) in which two vertices are adjacent if the corresponding two K<inf>k</inf>-subgraphs are contained in a common K<inf>k+1</inf>-subgraph in G. We give a unified characterization for nontrivial connected graphs G and F such that the Cartesian product G□F is a k-line graph. In particular for k = 3, this answers the question of Bagga (2004), yielding the necessary and suficient 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 ≥ 3, the k-line graph of a connected graph G is isomorphic to the line graph of G if and only if G = K<inf>k+2</inf>. Furthermore, we prove that the recognition problem of k-line graphs and that of k-anti-Gallai graphs are NP-complete for each k ≥ 3. © 2015, Australian National University. All rights reserved.

Actions (login required)

Edit Item