Affordable Access

Publisher Website

Tree representations of graphs

Authors
Journal
European Journal of Combinatorics
0195-6698
Publisher
Elsevier
Publication Date
Volume
28
Issue
4
Identifiers
DOI: 10.1016/j.ejc.2006.04.002

Abstract

Abstract A graph is chordal if and only if it is the intersection graph of some family of subtrees of a tree. Applying “tolerance” allows larger families of graphs to be represented by subtrees. A graph G is in the family [ Δ , d , t ] if there is a tree with maximum degree Δ 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. It is known that both [ 3 , 3 , 1 ] and [ 3 , 3 , 2 ] are equal to the family of chordal graphs. Furthermore, one can easily observe that every graph G belongs to [ 3 , 3 , t ] for some t . Denote by t ( G ) the minimum t so that G ∈ [ 3 , 3 , t ] . In this paper, we study t ( G ) and parameters t ( n ) = min { t : G ∈ [ 3 , 3 , t ] for every G ⊆ K n } and t bip ( n ) = min { t : G ∈ [ 3 , 3 , t ] for every G ⊆ K n , n } . In particular, our results imply that log n < t bip ( n ) ≤ 5 n 1 / 3 log 2 n and log ( n / 2 ) < t ( n ) ≤ 20 n 1 / 3 log 2 n .

There are no comments yet on this publication. Be the first to share your thoughts.