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.
Strongly Even-Cycle Decomposable Graphs / Huynh, T.; King, A. D.; Oum, S. -I.; Verdian-Rizi, M.. - In: JOURNAL OF GRAPH THEORY. - ISSN 0364-9024. - 84:2(2017), pp. 158-175. [10.1002/jgt.22018]
Strongly Even-Cycle Decomposable Graphs
Huynh T.;
2017
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.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.