A characterization of substar graphs
From MaRDI portal
Publication:401150
DOI10.1016/J.DAM.2014.05.033zbMATH Open1298.05276arXiv1405.0588OpenAlexW2078153212MaRDI QIDQ401150FDOQ401150
Authors: Felix Joos 
Publication date: 26 August 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Abstract: The intersection graphs of stars in some tree are known as substar graphs. In this paper we give a characterization of substar graphs by the list of minimal forbidden induced subgraphs. This corrects a flaw in the main result of Chang, Jacobson, Monma and West (Subtree and substar intersection numbers, Discrete Appl. Math. 44, 205-220 (1993)) and this leads to a different list of minimal forbidden induced subgraphs.
Full work available at URL: https://arxiv.org/abs/1405.0588
Recommendations
Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph operations (line graphs, products, etc.) (05C76)
Cites Work
- Graph Classes: A Survey
- Intersection graphs of paths in a tree
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- A recognition algorithm for the intersection graphs of paths in trees
- Betweenness, orders and interval graphs
- Characterizing intersection graphs of substars of a star.
- Subtree and substar intersection numbers
Cited In (6)
This page was built for publication: A characterization of substar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q401150)
