Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Representations of Holes

28^th January 2014, 16:00 Ashton Lecture Theater
Dr. Mordo Shalom
Tel-Hai College
Israel

Abstract

Given a tree and a set P of non-trivial simple paths on it, VPT(P) is the VPT graph (i.e. the vertex intersection graph) of the paths P, and EPT(P) is the EPT graph (i.e. the edge intersection graph) of P. These graphs have been extensively studied in the literature.
Given two (edge) intersecting paths in a graph, their split vertices is the set of vertices having degree at least 3 in their union. A pair of (edge) intersecting paths is termed non-splitting if they do not have split vertices (namely if their union is a path).
We define the graph ENPT(P) of edge intersecting non-splitting paths of a tree, termed the ENPT graph, as the graph having a vertex for each path in P, and an edge between every pair of vertices representing two paths that are both edge-intersecting and non-splitting. A graph G is an ENPT graph if there is a tree T and a set of paths P of T such that G=ENPT(P), and we say that is a representation of G.

Our work follows Golumbic and Jamison's research [GJ85a, GJ85b], in which they defined the EPT graph class, and characterized the representations of chordless cycles (holes). We first show that cycles, trees and complete graphs are ENPT graphs. Our main goal is the characterization of the representations of chordless ENPT cycles. We use the results of [GJ85a,GJ85b] as building blocks in order to discover this characterization, which turn out to have a more complex structure than in the case of EPT holes. To achieve this goal, we first assume that the EPT graph induced by the vertices of an ENPT hole is given. We introduce three assumptions (P1), (P2), (P3) defined on EPT, ENPT pairs of graphs. We first characterize the representations of ENPT holes that satisfy (P1), (P2), (P3). We then relax two of these three assumptions and characterize the representations of ENPT holes satisfying (P3). These two results are achieved by providing polynomial-time algorithms. Last we show that the problem of finding such a representation is NP-Hard in general, i.e. without assumption (P3). This result extends in some sense the NP-Hardness of EPT graph recognition shown in [GJ85a].