Almost Resolvable Maximum Packings of Complete Graphs with 4-Cycles

Billington, Elizabeth J., Dejter, Italo J., Hoffman, D. G. and Lindner, C. C. (2011) Almost Resolvable Maximum Packings of Complete Graphs with 4-Cycles. Graphs and Combinatorics, 27 2: 161-170. doi:10.1007/s00373-010-0967-0

Author Billington, Elizabeth J.
Dejter, Italo J.
Hoffman, D. G.
Lindner, C. C.
Title Almost Resolvable Maximum Packings of Complete Graphs with 4-Cycles
Journal name Graphs and Combinatorics   Check publisher's open access policy
ISSN 0911-0119
Publication date 2011-03
Year available 2010
Sub-type Article (original research)
DOI 10.1007/s00373-010-0967-0
Open Access Status
Volume 27
Issue 2
Start page 161
End page 170
Total pages 10
Place of publication Tokyo, Japan
Publisher Springer Japan
Collection year 2012
Language eng
Formatted abstract
If the complete graph K𝑛 has vertex set X, a maximum packing of K𝑛 with 4-cycles, (X, C, L), is an edge-disjoint decomposition of K𝑛 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𝑛 with 4-cycles were shown to exist by Schönheim and Bialostocki (Can. Math. Bull. 18:703–708, 1975). An almost parallel class of a maximum packing (X, C, L) of K𝑛 with 4-cycles is a largest possible collection of vertex disjoint 4-cycles (so with ⌊𝑛/4⌋ 4-cycles in it). In this paper, for all orders 𝑛, except 9, which does not exist, and possibly 23, 41 and 57, we exhibit a maximum packing of K𝑛 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).]
Keyword 4-cycle system
Resolvable cycle system maximum packing
Almost resolvable maximum packing
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ
Additional Notes Published online: 7 August 2010

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
Official 2012 Collection
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 1 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 1 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 20 Sep 2011, 11:48:22 EST by Dr Elizabeth Billington on behalf of Mathematics