Local EPT graphs on bounded degree trees

LILIANA ALCÓN; MARISA GUTIERREZ; MARÍA PÍA MAZZOLENI

Montevideo

Conferencia; Foundations of Computational Mathematics conference; 2014

A graph G is called an EPT graph if it is the edge intersection graph of a family of paths in a tree. An EPT representation of G is a pair (P,T) where P is a family Pv, with v a vertex of G, of subpaths of the host tree T satisfying that two vertices v and v´ of G are adjacent if and only if Pv and Pv´ have at least two vertices (one edge) in common. When the maximum degree of  the hosttree T is at most h, the EPT representation of G is called an (h,2,2)-representation of G. The class of graphs which admit an (h,2,2)-representation is denoted by [h,2,2]. Notice that  the class of EPT graphs is the union of the classes [h,2,2] for h >1. It is proved that the recognition of EPT graphs is an NP-complete problem.The EPT graphs are used in network applications, where the problem of scheduling undirected calls in a tree network is equivalent to the problem ofcoloring an EPT graph.In this paper, we examine the local structure of paths passing through a given vertex of a host tree which has maximum degree h, and show these locally EPT graphs are equivalent to the line graphs of certain graphs.Definition:  Let (P,T) be an EPT representation of a graph G. A pie of size n is a star subgraph of T with central vertex q and neighbors q1,...,qn such that each "slice" qi,q,q(i+1) for 0 < i < n+1 is contained in a different member of P; addition is assumed to be module n. Let (P,T) be an EPT representation of a graph G. It was proved that if G contains a chordless cycle of length n>3, then (P,T) contains a pie of size n.Definition: We say that (P,T) is a local local EPT representation of G if it is an EPT representation where all the paths of P share a common vertex of T. We call G a local EPT graph if it has a local EPT representation.Let h > 4, we say that G belongs to the class [h,2,2] local if and only if G has a local EPT representation in a host tree T with maximum degree h.In this work, we characterize the graphs which belongs to the class [h,2,2] local.Definition: Let G be a connected graph. We say that a vertex v of G is a cut vertex of G if G-v has at least two connected components.Theorem 1: Let h > 4. If G is in the class  [h,2,2] local and G is not in the class [h-1,2,2] then G has no cut vertices.We show that this special subclass of EPT graphs is equivalent to the class of line graphs of certain graphs which have certain properties.Definition: Let H be a graph, the line graph of H, noted by L(H), has vertices corresponding to the edges of H with two vertices adjacent in L(H) if their corresponding edges of H share an endpoint.Definition: We say that two vertices u,v of G are adjacent dominated vertices if uv are adjacent in G and N(G(u)) contains N(G(v)) or N(G(v)) contains N(G(u)).Theorem 2: Let h >4. G is in the class [h,2,2] local, G is not in the class [h-1,2,2] and G without adjacent dominated vertices if and only if G=L(H) with H a graph such that: (i) |V(H)|=h; (ii) H has no vertices of degree 1; (iii) H is simple; (iv) H has no adjacent dominated vertices; (v) H has a cycle Cn, with 3< n< h+1, and every vertex of H-Cn is in some path between two different vertices of Cn.Conjecture: Let h > 4. If G is in the class [h,2,2], G is not in the class [h-1,2,2] but G-v is in the class [h-1,2,2], for all vertex v of G, then G is in the class [h,2,2] local.