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 of size is the maximum number of odd cycles in such a cycle decomposition is and is an integer such that where and are of the same parity, then there is a cycle decomposition of with exactly odd cycles. This conjecture is verified for the line graph of the complete graph.

Keywords

• line graph
• eulerian graph
• cycle decomposition