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

详细信息    查看全文

• 作者：Arman Boyacı^a ; ^{arman.boyaci@boun.edu.tr" class="auth_mail" title="E-mail the corresponding author} ; Tınaz Ekim^a ; ^{tinaz.ekim@boun.edu.tr" class="auth_mail" title="E-mail the corresponding author} ; Mordechai Shalom^a ; ^b ; ^{cmshalom@telhai.ac.il" class="auth_mail" title="E-mail the corresponding author} ; Shmuel Zaks^c ; ^d ; ^{zaks@cs.technion.ac.il" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Intersection graphs ; EPT graphs
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：31 December 2016
• 年：2016
• 卷：215
• 期：Complete
• 页码：47-60
• 全文大小：620 K

文摘

Given a tree and a set P$\mathcal{P}$ of non-trivial simple paths on it, Vpt(P)$\text{<small-caps>Vpt</small-caps>}\left(\mathcal{P}\right)$ is the VPT$\text{<small-caps>VPT</small-caps>}$ graph (i.e. the vertex intersection graph) of the paths P$\mathcal{P}$ of the tree T$T$, and Ept(P)$\text{<small-caps>Ept</small-caps>}\left(\mathcal{P}\right)$ is the EPT$\text{<small-caps>EPT</small-caps>}$ graph (i.e. the edge intersection graph) of P$\mathcal{P}$. These graphs have been extensively studied in the literature. Given two (edge) intersecting paths in a graph, their split vertices are the 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).

In this work, motivated by an application in all-optical networks, we define the graph Enpt(P)$\text{<small-caps>Enpt</small-caps>}\left(\mathcal{P}\right)$ of edge-intersecting non-splitting paths of a tree, termed the ENPT$\text{<small-caps>ENPT</small-caps>}$ graph, as the (edge) graph having a vertex for each path in P$\mathcal{P}$, and an edge between every pair of paths that are both edge-intersecting and non-splitting. A graph G$G$ is an ENPT$\text{<small-caps>ENPT</small-caps>}$ graph if there is a tree T$T$ and a set of paths P$\mathcal{P}$ of T$T$ such that G=Enpt(P)$G=\text{<small-caps>Enpt</small-caps>}\left(\mathcal{P}\right)$, and we say that 〈T,P〉$〈T,\mathcal{P}〉$ is a representation   of G$G$. We first show that cycles, trees and complete graphs are ENPT$\text{<small-caps>ENPT</small-caps>}$ graphs.

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