%0 Journal Article
%T On the oriented perfect path double cover conjecture
%J Bulletin of the Iranian Mathematical Society
%I Iranian Mathematical Society (IMS)
%Z 1017-060X
%A Bagheri Gh., B.
%A Omoomi, B.
%D 2015
%\ 02/01/2015
%V 41
%N 1
%P 189-200
%! On the oriented perfect path double cover conjecture
%K Keywords: Oriented perfect
%K path double cover
%K Oriented cycle
double cover
%R
%X 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.
%U http://bims.iranjournals.ir/article_597_a931117b555271ee48028056b0d0101b.pdf