On the oriented perfect path double cover conjecture

MaRDI QIDQ281085zbMATH OpenFDO

Authors Behrooz Bagheri Gh., Behnaz Omoomi

Publication date 10 May 2016

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

Full work available at URL https://arxiv.org/abs/1207.1961, http://bims.iranjournals.ir/article_597_70.html

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)

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.

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

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)