Strongly Even-Cycle Decomposable Graphs

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

doi:10.1002/jgt.22018

Strongly Even-Cycle Decomposable Graphs

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

Research output: Contribution to journal › Article › Research › peer-review

5 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 language	English
Pages (from-to)	158-175
Number of pages	18
Journal	Journal of Graph Theory
Volume	84
Issue number	2
DOIs	https://doi.org/10.1002/jgt.22018
Publication status	Published - 1 Feb 2017
Externally published	Yes

Keywords

cograph
cycle
Eulerian
even-cycle decomposition

Access to Document

10.1002/jgt.22018

Cite this

@article{9122912e3dc048869a01ecf613ea4c8f,

title = "Strongly Even-Cycle Decomposable Graphs",

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.",

keywords = "cograph, cycle, Eulerian, even-cycle decomposition",

author = "Tony Huynh and King, {Andrew D.} and Oum, {Sang Il} and Maryam Verdian-Rizi",

year = "2017",

month = feb,

day = "1",

doi = "10.1002/jgt.22018",

language = "English",

volume = "84",

pages = "158--175",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "John Wiley & Sons",

number = "2",

}

TY - JOUR

T1 - Strongly Even-Cycle Decomposable Graphs

AU - Huynh, Tony

AU - King, Andrew D.

AU - Oum, Sang Il

AU - Verdian-Rizi, Maryam

PY - 2017/2/1

Y1 - 2017/2/1

N2 - 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.

AB - 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.

KW - cograph

KW - cycle

KW - Eulerian

KW - even-cycle decomposition

UR - http://www.scopus.com/inward/record.url?scp=84955067449&partnerID=8YFLogxK

U2 - 10.1002/jgt.22018

DO - 10.1002/jgt.22018

M3 - Article

AN - SCOPUS:84955067449

SN - 0364-9024

VL - 84

SP - 158

EP - 175

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 2

ER -

Strongly Even-Cycle Decomposable Graphs

Abstract

Keywords

Access to Document

Other files and links

Cite this