Forests and trees among Gallai graphs

DOI10.1016/J.DISC.2014.09.003zbMATH Open1303.05165arXiv1312.3072OpenAlexW2041874779MaRDI QIDQ472964FDOQ472964

Dieter Rautenbach, Van Bang Le, Felix Joos

Publication date: 20 November 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: The Gallai graph $Gamma(G)$ of a graph $G$ has the edges of $G$ as its vertices and two distinct vertices $e$ and $f$ of $Gamma(G)$ are adjacent in $Gamma(G)$ if the edges $e$ and $f$ of $G$ are adjacent in $G$ but do not span a triangle in $G$. Clearly, $Gamma(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.

Full work available at URL: https://arxiv.org/abs/1312.3072

Recommendations

• Tree- and forest-perfect graphs
• Forests in random graphs
• The existence of \(f\)-forests and \(f\)-trees in graphs
• scientific article; zbMATH DE number 9665
• Perfect forests in graphs and their extensions
• scientific article; zbMATH DE number 7724227
• Decomposition of Finite Graphs Into Forests
• The forest number in several classes of regular graphs
• Forest in biquartic graphs
• Induced Forests in Regular Graphs with Large Girth

zbMATH Keywords

line graphtriangular line graphanti-Gallai graphGallai graph

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Title not available (Why is that?)
• Transitiv orientierbare Graphen
• Distance-hereditary graphs
• A characterization of ptolemaic graphs
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• A description of claw-free perfect graphs
• Gallai graphs and anti-Gallai graphs
• Gallai and anti-Gallai graphs of a graph
• On the hardness of recognizing triangular line graphs
• Title not available (Why is that?)
• Recognizing claw-free perfect graphs
• The Dimension of Finite and Infinite Comparability Graphs
• Title not available (Why is that?)

Cited In (9)

• The Gallai and anti-Gallai graphs of strongly regular graphs
• A survey of the studies on Gallai and anti-Gallai graphs
• Gallai and anti-Gallai graphs of a graph
• Note on Perfect Forests in Digraphs
• Oriented Forests in Directed Graphs
• WHICH TREES ARE UNIQUELY FRAMED BY THE HEAWOOD GRAPH?
• Gallai and anti-Gallai graph operators
• A combinatorial approach to Golomb forests
• Graphs with at most two trees in a forest-building process

This page was built for publication: Forests and trees among Gallai graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q472964)