TY - JOUR
ID - 597
TI - On the oriented perfect path double cover conjecture
JO - Bulletin of the Iranian Mathematical Society
JA - BIMS
LA - en
SN - 1017-060X
AU - Bagheri Gh., B.
AU - Omoomi, B.
AD - Isfahan University of Technology
AD -
Y1 - 2015
PY - 2015
VL - 41
IS - 1
SP - 189
EP - 200
KW - Keywords: Oriented perfect
KW - path double cover
KW - Oriented cycle
double cover
DO -
N2 - An oriented perfect path double cover (OPPDC) of a graph $G$ is a collection of directed paths in the symmetric orientation $G_s$ of $G$ such that each arc of $G_s$ lies in exactly one of the paths and each vertex of $G$ appears just once as a beginning and just once as an end of a path. Maxov{'a} and Ne{v{s}}et{v{r}}il (Discrete Math. 276 (2004) 287-294) conjectured that every graph except two complete graphs $K_3$ and $K_5$ has an OPPDC and they claimed that the minimum degree of the minimal counterexample to this conjecture is at least four. In the proof of their claim, when a graph is smaller than the minimal counterexample, they missed to consider the special cases $K_3$ and $K_5$. In this paper, among some other results, we present the complete proof for this fact. Moreover, we prove that the minimal counterexample to this conjecture is $2$-connected and $3$-edge-connected.
UR - http://bims.iranjournals.ir/article_597.html
L1 - http://bims.iranjournals.ir/article_597_a931117b555271ee48028056b0d0101b.pdf
ER -