Tree representations of graphs

DOI10.1016/J.EJC.2006.04.002MaRDI QIDQ875046zbMATH OpenOpenAlexFDO

Authors Nancy Eaton, Zoltán Füredi, Alexandr Kostochka, J. Skokan

Publication date 10 April 2007

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2006.04.002

zbMATH Keywords

chordal graph intersection graph tree representation

Mathematics Subject Classification ID

Trees (05C05) Graph representations (geometric and intersection representations, etc.) (05C62)

Review text

A graph \(G\) is in the family \([\Delta,d,t]\) if there is a tree with maximum degree \(\Delta\) and subtrees corresponding to the vertices of \(G\) such that each subtree has maximum degree at most \(d\) and two vertices of \(G\) are adjacent if and only if the subtrees corresponding to them have at least \(t\) common vertices. \textit{M. C. Golumbic} and \textit{R. E. Jamison} [Discrete Math. 55, 151--159 (1985; Zbl 0568.05023)] proved that both \([3,3,1]\) and \([3,3,2]\) are equal to the family of chordal graphs. The authors observe that every graph \(G\) belongs to \([3,3,t]\) for some \(t\) and study the minimum \(t\) so that \(G\in [3,3,t]\). Further, they study parameters \(t(n)=\min\{ t \mid G\in [3,3,t]\) for all \(G\subseteq K_n\}\) and \(t_{bip}(n)= \min\{ t \mid G\in [3,3,t]\) for all \(G\subseteq K_{n,n}\}\). Upper and lower bounds are given.

Recommendations

Cites work

Cited in

(20)

This page was built for publication: Tree representations of graphs

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