On the oriented perfect path double cover conjecture

zbMATH Open1335.05098arXiv1207.1961MaRDI QIDQ281085FDOQ281085

Authors: Behrooz Bagheri Gh., Behnaz Omoomi 

Publication date: 10 May 2016

Published in: Bulletin of the Iranian Mathematical Society (Search for Journal in Brave)

Abstract: An {sf oriented perfect path double cover} ($mOPPDC$) of a graph $G$ is a collection of directed paths in the symmetric orientation $G_s$ of $G$ such that each edge 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 $mOPPDC$ and they proved that the minimum degree of the minimal counterexample to this conjecture is at least four. In this paper, among some other results, we prove that the minimal counterexample to this conjecture is 2-connected and 3-edge-connected.

Full work available at URL: https://arxiv.org/abs/1207.1961

Recommendations

• On oriented path double covers
• On covers of graphs
• Perfect path double covers of graphs
• Small oriented cycle double cover of graphs
• Perfect path double covers in every simple graph

zbMATH Keywords

oriented cycle double coveroriented perfect path double coverperfect path double cover

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (4)

• On oriented path double covers
• On covers of graphs
• Small oriented cycle double cover of graphs
• Perfect path double covers of graphs

This page was built for publication: On the oriented perfect path double cover conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q281085)