Eulerian Cycle Decomposition Conjecture for the line graph of complete graphs

Abstract

The Eulerian Cycle Decomposition Conjecture, by Chartrand, Jordon and Zhang, states that if the minimum number of odd cycles in a cycle decomposition of an Eulerian graph G of size m is a, the maximum number of odd cycles in such a cycle decomposition is b and ℓ is an integer such that a≤ℓ≤b where ℓ and m are of the same parity, then there is a cycle decomposition of G with exactly ℓ odd cycles. This conjecture is verified for the line graph of the complete graph. Keywords: Line graph, Eulerian graph, Cycle decomposition