Graphs of edge-intersecting non-splitting paths in a tree: towards hole representations (extended abstract)

DOI10.1007/978-3-642-45043-3_11MaRDI QIDQ2864295zbMATH OpenOpenAlexFDO

Authors Arman Boyacı, Tınaz Ekim, Mordechai Shalom, Shmuel Zaks

Publication date 6 December 2013

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.2898

zbMATH Keywords

edge intersecting non-splitting paths of a tree (ENPT graph)representations of chordless ENPT cyclesvertex intersection graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: Given a tree and a set $calP$ of non-trivial simple paths on it, $VPT(calP)$ is the VPT graph (i.e. the vertex intersection graph) of the paths $calP$ of the tree $T$, and $EPT(calP)$ is the EPT graph (i.e. the edge intersection graph) of $calP$. These graphs have been extensively studied in the literature. Given two (edge) intersecting paths in a graph, their emph{split vertices} is the set of vertices having degree at least $3$ in their union. A pair of (edge) intersecting paths is termed emph{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(calP)$ of edge-intersecting non-splitting paths of a tree, termed the ENPT graph, as the (edge) graph having a vertex for each path in $calP$, and an edge between every pair of 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 $calP$ of $T$ such that $G=ENPT(calP)$, and we say that $<T,calP>$ is a emph{representation} of $G$. We first show that cycles, trees and complete graphs are ENPT graphs. Our work follows the lines of Golumbic and Jamison's research 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)$, $(P2)$, $(P3)$, and (b) the unique minimal representation of such pairs.

Recommendations

• Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. II
• Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I
• Graphs of edge-intersecting and non-splitting paths
• Edge and vertex intersection of paths in a tree
• Triangulated edge intersection graphs of paths in a tree

Cited in

(4)

• Graphs of edge-intersecting and non-splitting paths
• Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I
• Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. II
• Recognizing vertex intersection graphs of paths on bounded degree trees

This page was built for publication: Graphs of edge-intersecting non-splitting paths in a tree: towards hole representations (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2864295)