Almost Resolvable Maximum Packings of Complete Graphs with 4-Cycles

Autor: Dean G. Hoffman, Charles C. Lindner, Elizabeth J. Billington, Italo J. Dejter
Rok vydání: 2010
Předmět:
Zdroj: Graphs and Combinatorics. 27:161-170
ISSN: 1435-5914
0911-0119
DOI: 10.1007/s00373-010-0967-0
Popis: 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 $${\lfloor/4\rfloor}$$ 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).]
Databáze: OpenAIRE
Externí odkaz: