Forests and trees among Gallai graphs

DOI10.1016/J.DISC.2014.09.003MaRDI QIDQ472964zbMATH OpenOpenAlexFDO

Authors Felix Joos, Van Bang Le, Dieter Rautenbach

Publication date 20 November 2014

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

line graphtriangular line graphanti-Gallai graphGallai graph

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(11)

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

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)