2015/05/28 by Lalla Mouatadid, Robert Robere, Mouatadid, Lalla +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1505.07702
openalex publication_date 2015/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An asteroidal triple is a set of three independent vertices in a graph such that any two vertices in the set are connected by a path which avoids the neighbourhood of the third. A classical result by Lekkerkerker and Boland \cite6 showed that interval graphs are precisely the chordal graphs that do not have asteroidal triples. Interval graphs are chordal, as are the directed path graphs and the path graphs. Similar to Lekkerkerker and Boland, Cameron, Hoáng, and Lévêque \cite4 gave a characterization of directed path graphs by a "special type" of asteroidal triple, and asked whether or not there was such a characterization for path graphs. We give strong evidence that asteroidal triples alone are insufficient to characterize the family of path graphs, and give a new characterization of path graphs via a forbidden induced subgraph family that we call sun systems. Key to our new characterization is the study of asteroidal sets in sun systems, which are a natural generalization of asteroidal triples. Our characterization of path graphs by forbidding sun systems also generalizes a characterization of directed path graphs by forbidding odd suns that was given by Chaplick et al.~\cite9.