×

Signed Langford sequences and directed cyclic cycle systems. (English) Zbl 1465.05137

Summary: For positive integers \(d\) and \(t\), a Langford sequence of order \(t\) and defect \(d\) is a sequence \(\mathcal{L}^t_d=(s_1,\dots,s_{2t})\) of length \(2t\) that satisfies (i) for every \(k\in \{d,d+1,\dots,t+d-1\}\), there are exactly two elements \(s_i\), \(s_j\in\mathcal{L}^t_d\) such that \(s_i=s_j=k\) and (ii) if \(s_i=s_j=k\) with \(i<j\), then \(j-i=k\). Note that (ii) could be written as \(j-i-k=0\) or \(i+k-j=0\). Hence, one extension of a Langford sequence is as follows. For positive integers \(d\) and \(t\), a signed Langford sequence of order \(t\) and defect \(d\) is a sequence \(\pm\mathcal{L}^t_d=(s_{-2t},s_{-2t+1},\dots,s_{-1},\ast,s_1,\dots,s_{2t})\) of length \(4t+1\) that satisfies (i) for every \(k\in\{\pm d,\pm (d+1),\dots\pm (t+d-1)\}\), there are exactly two elements \(s_i\), \(s_j\in\pm\mathcal{L}^t_d\) such that \(s_i=s_j=k\) and (ii) if \(s_i=s_j=k\) with \(i<0<j\), then \(i+j+k=0\). Here we give necessary and sufficient conditions for the existence of a signed Langford sequence of order \(t\) and defect \(d\) for \(d\in\{1,2,3\}\). We also use these sequences to find cyclic decompositions of circulant digraphs into directed \(m\)-cycles for \(m\geq 3\). In particular, we find a cyclic \(m\)-cycle decomposition of the complete symmetric digraph \(K_{2m+1}^\ast\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: Link

References:

[1] A. Blinco, S. El Zanati and C. Vanden Eynden, On the cyclic decomposition of complete graphs into almost complete graphs,Discrete Math.284(2004), 71-81. · Zbl 1044.05057
[2] M. Buratti, Cycle decompositions with a sharply vertex transitive automorphism group,Le Matematiche59(2004), 91-105. · Zbl 1150.05021
[3] M. Buratti and A. Del Fra, Existence of cyclick-cycle systems of the complete graph,Discrete Math.261(2003), 113-125. · Zbl 1013.05023
[4] M. Buratti and A. Del Fra, Cyclic hamiltonian cycle systems of the complete graph,Discrete Math.279(2004), 107-119. · Zbl 1034.05030
[5] D. Bryant, H. Gavlas and A. C. H. Ling, Skolem-type difference sets for cycle systems,Electron. J. Combin.10(2003), #R38. · Zbl 1031.05102
[6] D. Bryant and C. A. Rodger, Cycle Decompositions, in:The CRC Handbook of Combinatorial Designa,2nd edition, (eds. C. J. Colbourn and J. H. Dinitz), CRC Press, Boca Raton FL (2007), 373-382.
[7] R. O. Davies, On Langford’s problem II,Math. Gaz.43(1959), 253-255. · Zbl 0116.01103
[8] S. I. El-Zanati, N. Punnim and C. Vanden Eynden, On the cyclic decomposition of complete graphs into bipartite graphs,Austral. J. Combin.24(2001), 209- 219. · Zbl 0983.05063
[9] N. Franceti´c and E. Mendelsohn, A survey of Skolem-type sequences and Rosa’s use of them,Mathematica Slovaca.59(2009), 39-76. · Zbl 1199.05001
[10] H.-L. Fu and S.-L. Wu, Cyclically decomposing complete graphs into cycles, Discrete Math.282(2004), 267-273. · Zbl 1042.05082
[11] H. Jordon and J. Morris, Directed cyclic hamiltonian cycle systems ofKn∗,Discrete Math.309(2009), 784-796. · Zbl 1162.05024
[12] A. Kotzig, On decompositions of the complete graph into 4k-gons,Mat.-Fyz. Cas.15(1965), 227-233.
[13] A. Rosa, On cyclic decompositions of the complete graph into (4m+ 2)-gons, Mat.-Fyz. Cas.16(1966), 349-352. · Zbl 0147.42803
[14] A. Rosa, On the cyclic decompositions of the complete graph into polygons with an odd number of edges,Casopis Pˇˇest. Math.91(1966), 53-63. · Zbl 0151.33501
[15] J. E. Simpson, Langford sequences: perfect and hooked,Discrete Math.44 (1983), 97-104. · Zbl 0514.05007
[16] Th. Skolem, On certain distributions of integers in pairs with given difference, Math. Scand.5(1957), 57-68. · Zbl 0084.04304
[17] A. Vietri, Cyclick-cycles systems of order 2kn+k; a solution of the last open cases,J. Combin. Des.12(2004), 299-310. · Zbl 1045.05025
[18] S.-L. Wu and H.-L. Fu, Cyclicm-cycle systems withm≤32 orm= 2qwithq a prime power,J. Combin. Des.14(2006), 66-81
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.