Even cycle decompositions of complete graphs minus a 1-factor

✍ Scribed by Brian Alspach; Susan Marshall

• Publisher: John Wiley and Sons
• Year: 1994
• Tongue: English
• Weight: 873 KB
• Volume: 2
• Category: Article
• ISSN: 1063-8539
• DOI: 10.1002/jcd.3180020607

✦ Synopsis

Some sufficient conditions are proven for the complete graph of even order with a 1-factor removed to be decomposable into even length cycles. 0 1994 John Wiley & Sons, Inc.

1. Introduction

It is natural to ask when a complete graph admits a decomposition into cycles of some fixed length. Since the existence of such a decomposition requires the degrees of the vertices to be even, it is immediately seen that the number of vertices in the complete graph must be odd. Many of the articles dealing with the question include this restriction. However the question can be extended to graphs with an even number of vertices by considering the graph Kzn -Z, the complete graph on 2n vertices with a 1-factor I deleted, in place of the complete graph K2,,. The question then becomes the following. For which n does the graph Kzn+, or Kzn -I admit a decomposition into cycles of length k, where k is fixed? There are two obvious necessary conditions: k 5 2n + 1 or k 5 2n must hold, and k must divide the number of edges in either K2n+1 or Kzn -I , whichever is appropriate. There is not one example known where these necessary conditions are not sufficient.

There have been many articles discussing this question, and we recommend an excellent new survey [6], as well as the older surveys [2,3]. Just how close are we to achieving an answer? A superficial examination of the results to date might lead *This research was partially supported by the Natural Sciences and Engineering Research Council of Cmada under Grant A-4792 and the Centre de Recerca Matemiticia, Institut d'Estudis Catalans.