On the oriented perfect path double cover conjecture

Document Type: Research Paper


Isfahan University of Technology


‎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‎.


Main Subjects

Volume 41, Issue 1
January and February 2015
Pages 189-200
  • Receive Date: 15 December 2012
  • Revise Date: 27 December 2013
  • Accept Date: 27 December 2013