Strongly even cycle decomposable 4-regular line graphs
W Liu, J Wang, Q Cui, Y Yang - European Journal of Combinatorics, 2021 - Elsevier
W Liu, J Wang, Q Cui, Y Yang
European Journal of Combinatorics, 2021•ElsevierA graph is even cycle decomposable if its edges can be partitioned into cycles of even
length. A graph G is strongly even cycle decomposable if every subdivision of G with an
even number of edges is even cycle decomposable. Markström conjectured that for any
simple 2-connected cubic graph G, its line graph L (G) is even cycle decomposable.
Máčajová and Mazák further asked whether L (G) is strongly even cycle decomposable. In
this paper, we resolve this question (as well as Markström's conjecture) in the affirmative for …
length. A graph G is strongly even cycle decomposable if every subdivision of G with an
even number of edges is even cycle decomposable. Markström conjectured that for any
simple 2-connected cubic graph G, its line graph L (G) is even cycle decomposable.
Máčajová and Mazák further asked whether L (G) is strongly even cycle decomposable. In
this paper, we resolve this question (as well as Markström's conjecture) in the affirmative for …
A graph is even cycle decomposable if its edges can be partitioned into cycles of even length. A graph G is strongly even cycle decomposable if every subdivision of G with an even number of edges is even cycle decomposable. Markström conjectured that for any simple 2-connected cubic graph G, its line graph L (G) is even cycle decomposable. Máčajová and Mazák further asked whether L (G) is strongly even cycle decomposable. In this paper, we resolve this question (as well as Markström’s conjecture) in the affirmative for a class of cubic graphs. We prove that for a (not necessarily simple) 2-connected cubic graph G, if there exists a cycle C in G such that G− V (C) is a linear forest (ie, a forest whose components are paths), then L (G) is strongly even cycle decomposable. Our main motivation for considering this class of graphs comes from a conjecture of Ash and Jackson that every cyclically 4-edge-connected cubic graph has a dominating cycle (ie, a cycle whose deletion results in an independent set of vertices). If this conjecture is true, then our result will imply that the line graph of every cyclically 4-edge-connected cubic graph is strongly even cycle decomposable.
Elsevier
Showing the best result for this search. See all results