Almost Resolvable Maximum Packings of Complete Graphs with 4-Cycles

作者：Billington Elizabeth J^*; Dejter Italo J; Hoffman D G; Lindner C C

来源：Graphs and Combinatorics, 2011, 27(2): 161-170.

DOI：10.1007/s00373-010-0967-0

• 4-Cycle system
• Resolvable cycle system maximum packing
• Almost resolvable maximum packing

If the complete graph K (n) has vertex set X, a maximum packing of K (n) with 4-cycles, (X, C, L), is an edge-disjoint decomposition of K (n) into a collection C of 4-cycles so that the unused edges (the set L) is as small a set as possible. Maximum packings of K (n) with 4-cycles were shown to exist by Schonheim and Bialostocki (Can. Math. Bull. 18:703-708, 1975). An almost parallel class of a maximum packing (X, C, L) of K (n) with 4-cycles is a largest possible collection of vertex disjoint 4-cycles (so with left perpendicularn/4right perpendicular 4-cycles in it). In this paper, for all orders n, except 9, which does not exist, and possibly 23, 41 and 57, we exhibit a maximum packing of K (n) with 4-cycles so that the 4-cycles in the packing are resolvable into almost parallel classes, with any remaining 4-cycles being vertex disjoint. [Note: The three missing orders have now been found, and appear in Billington et al. (to appear).].

• 出版日期2011-3