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.
Bagheri Gh., B., & Omoomi, B. (2015). On the oriented perfect path double cover conjecture. Bulletin of the Iranian Mathematical Society, 41(1), 189-200.
MLA
Bagheri Gh., B., & Omoomi, B. "On the oriented perfect path double cover conjecture", Bulletin of the Iranian Mathematical Society, 41, 1, 2015, 189-200.
HARVARD
Bagheri Gh. B., Omoomi B. (2015). 'On the oriented perfect path double cover conjecture', Bulletin of the Iranian Mathematical Society, 41(1), pp. 189-200.
CHICAGO
B. Bagheri Gh. & B. Omoomi, "On the oriented perfect path double cover conjecture," Bulletin of the Iranian Mathematical Society, 41 1 (2015): 189-200,
VANCOUVER
Bagheri Gh. B., Omoomi B. On the oriented perfect path double cover conjecture. BIMS. 2015;41(1):189-200.
