2013/12/11 by Felix Joos, Van Bang Le, Joos, Felix +4
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1312.3072
14 pages
arxiv created 2013/12/11 · openalex publication_date 2013/12/11 · arxiv updated 2013/12/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Gallai graph Γ(G) of a graph G has the edges of G as its vertices and two distinct vertices e and f of Γ(G) are adjacent in Γ(G) if the edges e and f of G are adjacent in G but do not span a triangle in G. Clearly, Γ(G) is a subgraph of the line graph of G. While line graphs can be recognized efficiently the complexity of recognizing Gallai graphs is unknown. In the present paper we characterize those graphs whose Gallai graphs are forests or trees, respectively.