2017/03/24 by Bornstein, Claudson Ferreira, Pinto, José Wilson Coura, Rautenbach, Dieter +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1703.08465
A graph G belongs to the class \rm ORTH[h,s,t] for integers h, s, and t if there is a pair (T,\cal S), where T is a tree of maximum degree at most h, and \cal S is a collection (Su)u∈ V(G) of subtrees Su of maximum degree at most s of T, one for each vertex u of G, such that, for every vertex u of G, all leaves of Su are also leaves of T, and, for every two distinct vertices u and v of G, the following three properties are equivalent: (i) u and v are adjacent. (ii) Su and Sv have at least t vertices in common. (iii) Su and Sv share a leaf of T. The class \rm ORTH[h,s,t] was introduced by Jamison and Mulder. Here we focus on the case s=2, which is closely related to the well-known VPT and EPT graphs. We collect general properties of the graphs in \rm ORTH[h,2,t], and provide a characterization in terms of tree layouts. Answering a question posed by Golumbic, Lipshteyn, and Stern, we show that \rm ORTH[h+1,2,t]∖ \rm ORTH[h,2,t] is non-empty for every h≥ 3 and t≥ 3. We derive decomposition properties, which lead to efficient recognition algorithms for the graphs in \rm ORTH[h,2,2] for every h≥ 3. Finally, we give a complete description of the graphs in \rm ORTH[3,2,2], and show that the graphs in \rm ORTH[3,2,3] are line graphs of planar graphs.