A characterization of substar graphs

DOI10.1016/J.DAM.2014.05.033MaRDI QIDQ401150zbMATH OpenOpenAlexFDO

Authors Felix Joos

Publication date 26 August 2014

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

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

zbMATH Keywords

intersection graphchordal graphsubstar graph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph operations (line graphs, products, etc.) (05C76)

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.

Recommendations

• Characterizing intersection graphs of substars of a star.
• scientific article; zbMATH DE number 1229625
• Intersection graph of maximal stars
• Subtree and substar intersection numbers
• Characterizing path graphs by forbidden induced subgraphs

Cites work

• A recognition algorithm for the intersection graphs of paths in trees
• Betweenness, orders and interval graphs
• Characterizing intersection graphs of substars of a star.
• Graph Classes: A Survey
• Intersection graphs of paths in a tree
• Subtree and substar intersection numbers
• The intersection graphs of subtrees in trees are exactly the chordal graphs

Cited in

(6)

• Characterizing intersection graphs of substars of a star.
• Well-partitioned chordal graphs
• Intersection graph of maximal stars
• Subtree and substar intersection numbers
• A characterization of star-symmetric hypergraphs
• Structure connectivity and substructure connectivity of star graphs

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)