Strongly even-cycle decomposable graphs

DOI10.1002/JGT.22018MaRDI QIDQ2958205zbMATH OpenOpenAlexFDO

Authors Tony Huynh, Andrew D. King, Sang-Il Oum, Maryam Verdian-Rizi

Publication date 1 February 2017

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

cycleEulerian graphcographeven-cycle decomposition

Mathematics Subject Classification ID

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

Abstract: A graph is strongly even-cycle decomposable if the edge set of every subdivision with an even number of edges can be partitioned into cycles of even length. We prove that several fundamental composition operations that preserve the property of being Eulerian also yield strongly even-cycle decomposable graphs. As an easy application of our theorems, we give an exact characterization of the set of strongly even-cycle decomposable cographs.

Recommendations

• Strongly even cycle decomposable 4-regular line graphs
• Even cycle decompositions of 4-regular graphs and line graphs
• On even circuit decompositions of eulerian graphs
• Decompositions of complete multipartite graphs into cycles of even length
• Even-cycle decompositions of graphs with no odd-K₄-minor

Cites work

• (Some of) the many uses of Eulerian graphs in graph theory (plus some applications)
• Complement reducible graphs
• Even circuits in planar graphs
• Even cycle decompositions of 4-regular graphs and line graphs
• On even circuit decompositions of eulerian graphs

Cited in

(5)

• Cycle intersection graphs and minimum decycling sets of even graphs
• Negative (and positive) circles in signed graphs: a problem collection
• On 4-connected 4-regular graphs without even cycle decompositions
• Strongly even cycle decomposable 4-regular line graphs
• Strongly even cycle decomposable non-planar line graphs

This page was built for publication: Strongly even-cycle decomposable graphs

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