Constant threshold intersection graphs of orthodox paths in trees

Abstract: A graph

G

belongs to the class

m O R T H [h, s, t]

for integers

h

,

s

, and

t

if there is a pair

(T, c a l S)

, where

T

is a tree of maximum degree at most

h

, and

c a l S

is a collection

(S_{u})_{u i n V (G)}

of subtrees

S_{u}

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

S_{u}

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)

S_{u}

and

S_{v}

have at least

t

vertices in common. (iii)

S_{u}

and

S_{v}

share a leaf of

T

. The class

m O R T H [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

m O R T H [h, 2, t]

, and provide a characterization in terms of tree layouts. Answering a question posed by Golumbic, Lipshteyn, and Stern, we show that

m O R T H [h + 1, 2, t] s e t m i n u s m O R T H [h, 2, t]

is non-empty for every

h g e q 3

and

t g e q 3

. We derive decomposition properties, which lead to efficient recognition algorithms for the graphs in

m O R T H [h, 2, 2]

for every

h g e q 3

. Finally, we give a complete description of the graphs in

m O R T H [3, 2, 2]

, and show that the graphs in

m O R T H [3, 2, 3]

are line graphs of planar graphs.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Constant threshold intersection graphs of orthodox paths in trees