zbMATH — the first resource for mathematics

Hamilton decompositions of 6-regular Cayley graphs on even abelian groups with involution-free connections sets. (English) Zbl 1297.05115
Summary: B. Alspach [“Research problem 59”, ibid. 50, 115 (1984)] conjectured that every connected Cayley graph on a finite abelian group $$A$$ is Hamilton-decomposable. J. Liu [ibid. 131, No. 1–3, 163–171 (1994; Zbl 0809.05058)] has shown that for $$| A |$$ even, if $$S = \{s_1, \ldots, s_k \} \subset A$$ is an inverse-free strongly minimal generating set of $$A$$, then the Cayley graph Cay$$(A; S^\star)$$, is decomposable into $$k$$ Hamilton cycles, where $$S^\star$$ denotes the inverse-closure of $$S$$. Extending these techniques and restricting to the $$6$$-regular case, this article relaxes the constraint of strong minimality on $$S$$ to require only that $$S$$ be strongly $$a$$-minimal, for some $$a \in S$$ and the index of $$\langle a \rangle$$ be at least four. Strong $$a$$-minimality means that $$2 s \notin \langle a \rangle$$ for all $$s \in S \smallsetminus \{a, - a \}$$. Some infinite families of open cases for the 6-regular Cayley graphs on even-order abelian groups are resolved. In particular, if $$| s_1 | \geq | s_2 | > 2 | s_3 |$$, then $$\mathrm{Cay}(A; \{s_1, s_2, s_3 \}^\star)$$ is Hamilton-decomposable.

MSC:
 05C25 Graphs and abstract algebra (groups, rings, fields, etc.) 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C45 Eulerian and Hamiltonian graphs 05C38 Paths and cycles
Magma
Full Text:
References:
 [1] Combinatorial structures and their applications, (Proceedings of the Calgary International Conference on Combinatorial Structures and their Applications held at the University of Calgary, Calgary, Alberta, Canada, June, vol. 1969, (1970), New York) [2] Alspach, B., Research problem 59, Discrete Math., 50, 115, (1984) [3] Alspach, Brian; Caliskan, Cafer; Kreher, Donald L., Orthogonal projection and liftings of Hamilton-decomposable Cayley graphs on abelian groups, Discrete Math., 313, 13, 1475-1489, (2013) · Zbl 1279.05034 [4] Alspach, B.; Heinrich, K.; Liu, G. Z., Orthogonal factorizations of graphs, (Contemporary Design Theory, Wiley-Intersci. Ser. Discrete Math. Optim., (1992), Wiley New York), 13-40 · Zbl 0779.05032 [5] Bermond, J.-C.; Favaron, O.; Mahéo, M., Hamiltonian decomposition of Cayley graphs of degree 4, J. Combin. Theory Ser. B, 46, 2, 142-153, (1989) · Zbl 0618.05032 [6] Bondy, J. A., Hamilton cycles in graphs and digraphs, (Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing, (Florida Atlantic Univ., Boca Raton, Fla., 1978) (Winnipeg, Man.), Congress. Numer., XXI, (1978), Utilitas Math.), 3-28, MR 527929 (80k:05074) · Zbl 0406.05046 [7] Bosma, W.; Cannon, J.; Playoust, C., The magma algebra system. I. the user language, J. Symbolic Comput., 24, 3-4, 235-265, (1997), Computational algebra and number theory (London, 1993). MR 1484478 · Zbl 0898.68039 [8] Chen, C. C.; Quimpo, N. F., On strongly Hamiltonian abelian group graphs, (Combinatorial Mathematics, VIII (Geelong, 1980), Lecture Notes in Math., vol. 884, (1981), Springer Berlin), 23-34 [9] Curran, S. J.; Gallian, J. A., Hamiltonian cycles and paths in Cayley graphs and digraphs—a survey, Discrete Math., 156, 1-3, 1-18, (1996) · Zbl 0857.05067 [10] Dean, M., On Hamilton cycle decomposition of 6-regular circulant graphs, Graphs Combin., 22, 3, 331-340, (2006) · Zbl 1108.05057 [11] Dean, M., Hamilton cycle decomposition of 6-regular circulants of odd order, J. Combin. Des., 15, 2, 91-97, (2007) · Zbl 1113.05081 [12] Fan, C.; Lick, D. R.; Liu, J., Pseudo-cartesian product and Hamiltonian decompositions of Cayley graphs on abelian groups, Discrete Math., 158, 1-3, 49-62, (1996) · Zbl 0869.05046 [13] Li, H.; Wang, J.; Sun, L., Hamiltonian decomposition of Cayley graphs of orders $$p^2$$ and $$p q$$, Acta Math. Appl. Sin. Engl. Ser., 16, 1, 78-86, (2000), MR 1757325 · Zbl 0962.05022 [14] Liu, J., Hamiltonian decompositions of Cayley graphs on abelian groups, Discrete Math., 131, 1-3, 163-171, (1994) · Zbl 0809.05058 [15] Liu, J., Hamiltonian decompositions of Cayley graphs on abelian groups of odd order, J. Combin. Theory Ser. B, 66, 1, 75-86, (1996) · Zbl 0840.05069 [16] Liu, J., Hamiltonian decompositions of Cayley graphs on abelian groups of even order, J. Combin. Theory Ser. B, 88, 2, 305-321, (2003) · Zbl 1021.05047 [17] Marušič, Dragan, Hamiltonian circuits in Cayley graphs, Discrete Math., 46, 1, 49-54, (1983), MR 708161 (85a:05039) · Zbl 0515.05042 [18] Westlund, E. E., Hamilton decompositions of certain 6-regular Cayley graphs on abelian groups with a cyclic subgroup of index two, Discrete Math., 312, 3228-3235, (2012) · Zbl 1250.05090 [19] Westlund, E. E.; Liu, J.; Kreher, D. L., 6-regular Cayley graphs on abelian groups of odd order are Hamiltonian decomposable, Discrete Math., 309, 16, 5106-5110, (2009) · Zbl 1207.05084
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.