Strongly Even-Cycle Decomposable Graphs

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

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)158-175
Number of pages18
JournalJournal of Graph Theory
Volume84
Issue number2
DOIs
Publication statusPublished - 1 Feb 2017
Externally publishedYes

Keywords

  • cograph
  • cycle
  • Eulerian
  • even-cycle decomposition

Cite this

Huynh, T., King, A. D., Oum, S. I., & Verdian-Rizi, M. (2017). Strongly Even-Cycle Decomposable Graphs. Journal of Graph Theory, 84(2), 158-175. https://doi.org/10.1002/jgt.22018