Premium
Orthogonal double covers by super‐extendable cycles
Author(s) -
Bey Christian,
Hartmann Sven,
Leck Uwe,
Leck Volker
Publication year - 2002
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.10011
Subject(s) - mathematics , combinatorics , hamiltonian path , hamiltonian (control theory) , graph , discrete mathematics , mathematical optimization
An Orthogonal Double Cover (ODC) of the complete graph K n by an almost‐hamiltonian cycle is a decomposition of 2 K n into cycles of length n −1 such that the intersection of any two of them is exactly one edge. We introduce a new class of such decompositions. If n is a prime, the special structure of such a decomposition allows to expand it to an ODC of K n +1 by an almost‐hamiltonian cycle. This yields the existence of an ODC of K p +1 by an almost‐hamiltonian cycle for primes p of order 3 mod 4 and its eventual existence for arbitrary primes p . © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 283–293, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10011