Subtree and substar intersection numbers

DOI10.1016/0166-218X(93)90232-DMaRDI QIDQ686262zbMATH OpenOpenAlexFDO

Authors Yi-Wu Chang, Douglas B. West, Michael Jacobson, Clyde l. Monma

Publication date 24 February 1994

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

Full work available at URL https://doi.org/10.1016/0166-218x(93)90232-d

zbMATH Keywords

boundscliqueintersection numbersinterval numbersstar numbertree number

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Review text

The authors define the tree number of a graph \(G\) to be the minimum \(t\) such that \(G\) has an intersection representation in which to each vertex of \(G\) a union of \(t\) subtrees of an underlying tree is assigned. In the case all subtrees are stars they speak of the star number. A variety of results on the introduced invariants are presented, mostly bounds in terms of the clique, the interval numbers, etc.

Recommendations

• The 2‐intersection number of paths and bounded‐degree trees
• A characterization of substar graphs
• Onp-intersection representations
• Constant tolerance intersection graphs of subtrees of a tree
• Tree representations of graphs

Cites work

• A recognition algorithm for the intersection graphs of paths in trees
• A short proof of the degree bound for interval number
• An improved edge bound on the interval number of a graph
• Decomposition of Finite Graphs Into Forests
• Edge and vertex intersection of paths in a tree
• Extremal Values of the Interval Number of a Graph
• Extremal values of the interval number of a graph. II
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3906537 (Why is no real title available?)
• Minimum partition of a matroid into independent subsets
• On dimensional properties of graphs
• On the interval number of a chordal graph
• The edge intersection graphs of paths in a tree
• The interval number of a planar graph: Three intervals suffice
• When the cartesian product of directed cycles is Hamiltonian

Cited in

(5)

• Representing triangulated graphs in stars
• Interval numbers of powers of block graphs
• Well-partitioned chordal graphs
• Proof of a conjecture about minimum spanning tree cycle intersection
• A characterization of substar graphs

This page was built for publication: Subtree and substar intersection numbers

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