×

Orthogonal double covers by super-extendable cycles. (English) Zbl 1007.05080

This paper studies orthogonal double covers of the complete graph by almost Hamiltonian cycles, i.e. decompositions of \(2K_n\) by cycles of length \(n-1\) which pairwise share exactly one edge. Such covers were known to exist for \(n\) and odd prime power [B. Alspach, K. Heinrich and M. Rosenfeld, Isr. J. Math. 40, 118-128 (1981; Zbl 0472.05027)]. Here the authors introduce a new class of such decompositions which shows that they exist for \(n=q+1\) when \(q=2^et+1\) is a prime power and \(t\) is large enough. By specializing with \(e=1\), they show that the decompositions exist for \(n=q+1\) and \(q \equiv 3 \pmod 4\) a prime.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles

Citations:

Zbl 0472.05027
Full Text: DOI

References:

[1] and Orthogonal factorizations of graphs; contemporary design theory, chapter 2, and (Editors), Wiley, NewYork, 1992, pp. 13-40.
[2] Alspach, Israel J Math 40 pp 118– (1981)
[3] Dinitz, J Graph Theory 13 pp 405– (1989)
[4] and Room squares and related designs; contemporary design theory, chapter 5, and (Editors), Wiley, New York, 1992, pp. 137-204. · Zbl 0768.05015
[5] Ganter, Ars Combin 37 pp 209– (1994)
[6] personal communication.
[7] Gronau, Designs Codes Cryptogr (2002)
[8] Hartmann, Graphs and Combin (2002)
[9] Heinrich, Ann Discrete Math 27 pp 275– (1985)
[10] Hering, Ann Discrete Math 6 pp 201– (1980)
[11] Hering, Ann Discrete Math 20 pp 177– (1984)
[12] Lenstra, Math Comp 48 pp 217– (1987)
[13] and Finite fields, CUP, Cambridge, 1987.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.