Tree representations of graphs (Q875046)

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.