Graphs of edge-intersecting non-splitting paths in a tree: Representations of holes-Part I

Our work follows the lines of Golumbic and Jamison's research (Golumbic and Jamison, 1985) in which they defined the EPT graph class, and characterized the representations of chordless cycles (holes). It turns out that ENPT holes have a more complex structure than EPT holes. In our analysis, we assume that the EPT graph corresponding to a representation of an ENPT hole is given. We also introduce three assumptions (P1), (P2), (P3) defined on EPT, ENPT pairs of graphs. In this Part I, using the results of Golumbic and Jamison as building blocks, we characterize (a) EPT, ENPT pairs that satisfy (P1)-(P3), and (b) the unique minimal representation of such pairs.