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