کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419830 | 683866 | 2008 | 13 صفحه PDF | دانلود رایگان |
An (h,s,t)(h,s,t)-representation of a graph GG consists of a collection of subtrees of a tree TT, where each subtree corresponds to a vertex in GG, such that (i) the maximum degree of TT is at most hh, (ii) every subtree has maximum degree at most ss, (iii) there is an edge between two vertices in the graph GG if and only if the corresponding subtrees have at least tt vertices in common in TT. The class of graphs that have an (h,s,t)(h,s,t)-representation is denoted by [h,s,t][h,s,t]. It is well known that the class of chordal graphs corresponds to the class [3, 3, 1]. Moreover, it was proved by Jamison and Mulder that chordal graphs correspond to orthodox-[3, 3, 1] graphs defined below.In this paper, we investigate the class of [h,2,t][h,2,t] graphs, i.e., the intersection graphs of paths in a tree. The [h,2,1][h,2,1] graphs are also known as path graphs [F. Gavril, A recognition algorithm for the intersection graphs of paths in trees, Discrete Math. 23 (1978) 211–227] or VPT graphs [M.C. Golumbic, R.E. Jamison, Edge and vertex intersection of paths in a tree, Discrete Math. 55 (1985) 151–159], and [h,2,2][h,2,2] graphs are known as the EPT graphs. We consider variations of [h,2,t][h,2,t] by three main parameters: hh, tt and whether the graph has an orthodox representation. We give the complete hierarchy of relationships between the classes of weakly chordal, chordal, [h,2,t][h,2,t] and orthodox-[h,2,t][h,2,t] graphs for varied values of hh and tt.
Journal: Discrete Applied Mathematics - Volume 156, Issue 17, 28 October 2008, Pages 3203–3215