Geodesic
Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Representations of Holes-Part II
Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1.

Voir la notice de l'article provenant de la source Episciences

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 <T,P> is a representation of G. Our goal is to characterize the representation of chordless ENPT cycles (holes). To achieve this goal, we first assume that the EPT graph induced by the vertices of an ENPT hole is given. In [2] we introduce three assumptions (P1), (P2), (P3) defined on EPT, ENPT pairs of graphs. In the same study, we define two problems HamiltonianPairRec, P3-HamiltonianPairRec and characterize the representations of ENPT holes that satisfy (P1), (P2), (P3). In this work, we continue our work by relaxing these three assumptions one by one. We characterize the representations of ENPT holes satisfying (P3) by providing a polynomial-time algorithm to solve P3-HamiltonianPairRec. We also show that there does not exist a polynomial-time algorithm to solve HamiltonianPairRec, unless P=NP. 
@article{DMTCS_2018_20_1_a1,
     author = {Boyac{\i}, Arman and Ekim, T{\i}naz and Shalom, Mordechai and Zaks, Shmuel},
     title = {Graphs of {Edge-Intersecting} {Non-Splitting} {Paths} in a {Tree:} {Representations} of {Holes-Part} {II}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2018},
     doi = {10.23638/DMTCS-20-1-2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-2/}
}
TY  - JOUR
AU  - Boyacı, Arman
AU  - Ekim, Tınaz
AU  - Shalom, Mordechai
AU  - Zaks, Shmuel
TI  - Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Representations of Holes-Part II
JO  - Discrete mathematics & theoretical computer science
PY  - 2018
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-2/
DO  - 10.23638/DMTCS-20-1-2
LA  - en
ID  - DMTCS_2018_20_1_a1
ER  - 
%0 Journal Article
%A Boyacı, Arman
%A Ekim, Tınaz
%A Shalom, Mordechai
%A Zaks, Shmuel
%T Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Representations of Holes-Part II
%J Discrete mathematics & theoretical computer science
%D 2018
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-2/
%R 10.23638/DMTCS-20-1-2
%G en
%F DMTCS_2018_20_1_a1
Boyacı, Arman; Ekim, Tınaz; Shalom, Mordechai; Zaks, Shmuel. Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Representations of Holes-Part II. Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1. doi : 10.23638/DMTCS-20-1-2. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-2/

Cité par Sources :