ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P2.05
https://doi.org/10.26493/1855-3974.2692.86d
(Also available at http://amc-journal.eu)
Mutually orthogonal cycle systems*
Andrea C. Burgess †
Department of Mathematics and Statistics, University of New Brunswick,
Saint John, NB, E2L 4L5, Canada
Nicholas J. Cavenagh
Department of Mathematics, The University of Waikato, Private Bag 3105,
Hamilton 3240, New Zealand
David A. Pike
Department of Mathematics and Statistics, Memorial University of Newfoundland,
St. John’s, NL, A1C 5S7, Canada
Received 8 September 2021, accepted 23 June 2022, published online 17 November 2022
Abstract
An ℓ-cycle system F of a graph Γ is a set of ℓ-cycles which partition the edge set of
Γ. Two such cycle systems F and F ′ are said to be orthogonal if no two distinct cycles
from F ∪F ′ share more than one edge. Orthogonal cycle systems naturally arise from face
2-colourable polyehdra and in higher genus from Heffter arrays with certain orderings. A
set of pairwise orthogonal ℓ-cycle systems of Γ is said to be a set of mutually orthogonal
cycle systems of Γ.
Let µ(ℓ, n) (respectively, µ′(ℓ, n)) be the maximum integer µ such that there exists a
set of µ mutually orthogonal (cyclic) ℓ-cycle systems of the complete graph Kn. We show
that if ℓ ≥ 4 is even and n ≡ 1 (mod 2ℓ), then µ′(ℓ, n), and hence µ(ℓ, n), is bounded
below by a constant multiple of n/ℓ2. In contrast, we obtain the following upper bounds:
µ(ℓ, n) ≤ n − 2; µ(ℓ, n) ≤ (n − 2)(n − 3)/(2(ℓ − 3)) when ℓ ≥ 4; µ(ℓ, n) ≤ 1 when
ℓ > n/
√
2; and µ′(ℓ, n) ≤ n − 3 when n ≥ 4. We also obtain computational results for
small values of n and ℓ.
Keywords: Orthogonal cycle decompositions, cyclic cycle systems, Heffter arrays, completely-redu-
cible, super-simple.
Math. Subj. Class. (2020): 05B30
*Authors A.C. Burgess and D.A. Pike acknowledge research support from NSERC Discovery Grants RGPIN-
2019-04328 and RGPIN-2016-04456, respectively. Thanks are given to the Centre for Health Informatics and
Analytics of the Faculty of Medicine at Memorial University of Newfoundland for access to computational re-
sources.
†Corresponding author.
E-mail addresses: andrea.burgess@unb.ca (Andrea C. Burgess), nickc@waikato.ac.nz (Nicholas
J. Cavenagh), dapike@mun.ca (David A. Pike)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
ISSN 1855-3966 (tiskana izd.), ISSN 1855-3974 (elektronska izd.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P2.05
https://doi.org/10.26493/1855-3974.2692.86d
(Dostopno tudi na http://amc-journal.eu)
Medsebojno pravokotni ciklični sistemi*
Andrea C. Burgess †
Department of Mathematics and Statistics, University of New Brunswick,
Saint John, NB, E2L 4L5, Canada
Nicholas J. Cavenagh
Department of Mathematics, The University of Waikato, Private Bag 3105,
Hamilton 3240, New Zealand
David A. Pike
Department of Mathematics and Statistics, Memorial University of Newfoundland,
St. John’s, NL, A1C 5S7, Canada
Prejeto 8. septembra 2021, sprejeto 23. junija 2022, objavljeno na spletu 17. novembra 2022
Povzetek
ℓ-ciklični sistem F grafa Γ je množica ℓ-ciklov, ki razdelijo množico povezav grafa Γ.
Dva takšna ciklična sistema F in F ′ sta medsebojno pravokotna, če si nobena dva različna
cikla iz F∪F ′ ne delita več kot ene povezave. Pravokotni sistemi ciklov nastanejo naravno
iz poliedrov z 2-barvnim barvanjem lic, pri ploskvah višjega rodu pa iz Heffterjevih polj,
ki zadoščajo določenim pogojem. Množica paroma pravokotnih ℓ-cikličnih sistemov grafa
Γ je množica medsebojno pravokotnih cikličnih sistemov grafa Γ.
Naj bo µ(ℓ, n) (oziroma, µ′(ℓ, n)) maksimalno celo število µ, pri katerem obstaja
množica µ medsebojno pravokotnih (cikličnih) sistemov ℓ-ciklov polnega grafa Kn. Doka-
žemo: če je ℓ ≥ 4 sod in n ≡ 1 (mod 2ℓ), potem je µ′(ℓ, n), in torej tudi µ(ℓ, n), omejen
navzdol s konstantnim večkratnikom števila n/ℓ2. Dobimo tudi naslednje zgornje meje:
µ(ℓ, n) ≤ n − 2; µ(ℓ, n) ≤ (n − 2)(n − 3)/(2(ℓ − 3)), če je ℓ ≥ 4; µ(ℓ, n) ≤ 1, če je
ℓ > n/
√
2; in µ′(ℓ, n) ≤ n−3, če je n ≥ 4. Predstavimo tudi računske rezultate za majhne
vrednosti n in ℓ.
Ključne besede: Pravokotne ciklične dekompozicije, ciklični sistemi ciklov, Heffterjeva polja, popol-
noma reducibilen, superenostaven.
Math. Subj. Class. (2020): 05B30
*Avtorja A.C. Burgess in D.A. Pike ta imela raziskovalno podporo s strani raziskovalnih dotacij NSERC
RGPIN-2019-04328 oziroma RGPIN-2016-04456. Zahvaljujemo se Centre for Health Informatics and Analytics
of the Faculty of Medicine at Memorial University of Newfoundland za dostop do računalniških orodij.
†Kontaktni avtor.
E-poštni naslovi: andrea.burgess@unb.ca (Andrea C. Burgess), nickc@waikato.ac.nz (Nicholas
J. Cavenagh), dapike@mun.ca (David A. Pike)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/