×

zbMATH — the first resource for mathematics

Hamiltonian cycles and paths in Cayley graphs and digraphs—a survey. (English) Zbl 0857.05067
Let \(G\) be a group with \(e\) as its identity, and \(S\subseteq G\backslash\{e\}\) be a generating set of \(G\). The Cayley digraph \(\text{Cay}(S:G)\) is the directed graph with vertex set \(G\) and \(xy\) is an arc of the digraph if and only if there is an element \(g\in S\) such that \(xy=y\). The Cayley graph \(\text{Cay}(S:G)\) is undirected if \(g^{-1}\in S\) whenever \(g\in S\). This paper is a most comprehensive and updated survey article about the problem of Hamilton circuits and Hamilton paths in Cayley graphs since the 1984 survey paper by D. Witte and J. A. Gallian [Discrete Math. 51, No. 3, 293-304 (1984; Zbl 0712.05039)].

MSC:
05C45 Eulerian and Hamiltonian graphs
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C20 Directed graphs (digraphs), tournaments
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
PDF BibTeX Cite
Full Text: DOI
References:
[1] Alspach, B., Hamiltonian cycles in vertex-transitive graphs of order 2p, (), 131-139
[2] Alspach, B., Hamiltonian partitions of vertex-transitive graphs of order 2p, (), 217-221
[3] Alspach, B., Research problem 59, Discrete math., 50, 115, (1984)
[4] Alspach, B., Unsolved problem 4.5, Ann. discrete math., 27, 464, (1985)
[5] Alspach, B., Lifting Hamilton cycles of quotient graphs, Discrete math., 78, 25-36, (1989) · Zbl 0702.05054
[6] Alspach, B.; Bermond, J.-C.; Sotteau, D., Decompositions into cycles I: Hamilton decompositions, (), 9-18 · Zbl 0713.05047
[7] ()
[8] Alspach, B.; Heinrich, K.; Liu, G., Orthogonal factorizations of graphs, (), 13-40 · Zbl 0779.05032
[9] Alspach, B.; Zhang, C.Q., Hamilton cycles in cubic Cayley graphs on dihedral groups, Ars combin., 28, 101-108, (1989) · Zbl 0722.05047
[10] Annexstein, F.; Baumslag, M.; Rosenberg, A.L., Group action graphs and parallel architecture, SIAM J. comput., 19, 544-569, (1990) · Zbl 0698.68064
[11] L. Babai, Embedding graphs in Cayley graphs, in: Problèmes Combinatoires et Théorie des Graphes, Colloques Internationaux CNRS, No. 260, 13-15. · Zbl 0412.05037
[12] Barth, D.; Raspaud, A., Two disjoint Hamiltonian cycles in the butterfly graph, Inform. process. lett., 51, 175-179, (1994) · Zbl 0807.05047
[13] Bermond, J.-C., Hamilton decomposition of graphs, directed graphs and hypergraphs, (), 21-28 · Zbl 0382.05040
[14] Bermond, J.-C.; Favaron, O.; Maheo, M., Hamiltonian decomposition of Cayley graphs of degree 4, J. combin theory ser. B, 46, 142-153, (1989) · Zbl 0618.05032
[15] Chen, C.C., On edge-Hamiltonian property of Cayley graphs, Discrete math., 72, 29-33, (1988) · Zbl 0661.05030
[16] Chen, C.C.; Quimpo, N.F., On some classes of Hamiltonian groups, Southeast Asian bull. math., 252-258, (1979), Special issue · Zbl 0442.05044
[17] Chen, C.C.; Quimpo, N.F., On strongly Hamiltonian abelian group graphs, (), 23-34 · Zbl 0468.05055
[18] Chen, C.C.; Quimpo, N.F., Hamiltonian Cayley graphs of order pq, (), 1-5 · Zbl 0522.05042
[19] Compton, R.C.; Williamson, S.G., Doubly adjacent gray codes for the symmetric group, () · Zbl 0779.94004
[20] Conway, J.H.; Sloane, N.J.A.; Wilks, A.R., Gray codes for reflection groups, Graphs combin., 5, 315-325, (1989) · Zbl 0684.20036
[21] Coxeter, H.; Moser, W., Generators and relations for discrete groups, (1980), Springer New York · Zbl 0422.20001
[22] Curran, S.J., A generalization of a theorem of Rankin, (), 167-175 · Zbl 0765.05051
[23] Curran, S.J., Hamilton paths in Cayley digraphs on the semidirect product of cyclic groups, (), 209-221
[24] Curran, S.J., Hamilton paths in Cayley digraphs of metacyclic groups, Discrete math., 115, 133-139, (1993) · Zbl 0776.05049
[25] Curran, S.J., Disjoint circuits in the Cartesian product of directed cycles, J. graph theory, 18, 211-216, (1994) · Zbl 0792.05086
[26] Curran, S.J., Enumeration of Hamilton paths in Cayley digraphs on semidirect products of cyclic groups, (), 251-263 · Zbl 0843.05051
[27] S.J. Curran, Hamilton circuits in Cayley digraphs on abelian groups and dihedral groups, Preprint. · Zbl 1046.05049
[28] Curran, S.J.; Witte, D., Hamilton paths in Cartesian products of directed cycles, Ann. discrete math., 27, 35-74, (1985)
[29] Day, K.; Tripathi, A., Arrangement graphs: A class of generalized star graphs, Inform. process. lett., 42, 235-241, (1992) · Zbl 0772.68005
[30] Diaconis, P.; Holmes, S., Grey codes for randomization procedures, ()
[31] Dunham, D.; Jungreis, D.S.; Witte, D., Infinite Hamiltonian paths in Cayley digraphs of hyperbolic symmetry groups, Discrete math., 143, 1-30, (1995) · Zbl 0828.05031
[32] Dunham, D.; Lindgren, J.; Witte, D., Creating repeating hyperbolic patterns, Computer graphics, 15, 215-223, (1981)
[33] Durnberger, E., Connected Cayley graphs of semi-direct products of cyclic groups of prime order by abelian groups are Hamiltonian, Discrete math., 46, 55-68, (1983) · Zbl 0521.05046
[34] Durnberger, E., Every connected Cayley graph of a group with prime order commutator group has a Hamilton cycle, Ann. discrete math., 27, 75-80, (1985) · Zbl 0573.05027
[35] Epstein, D.B.A.; Cannon, J.W.; Holt, D.F.; Levy, S.V.F.; Paterson, M.S.; Thurston, W.P., Word processing in groups, (1992), Jones & Barlett
[36] Faber, V.; Moore, J.W., High-degree low-diameter interconnection networks with vertex-symmetry: the directed case, ()
[37] C. Fan, D. Lick, J. Liu, Pseudo-cartesian products and hamiltonian decompositions of Cayley graphs on abelian groups, Discrete Math., to appear. · Zbl 0869.05046
[38] Foregger, M.F., Hamiltonian decompositions of product cycles, Discrete math., 24, 251-260, (1978) · Zbl 0398.05055
[39] Gallian, J.A., Contemporary abstract algebra, (1994), D.C. Heath Lexington · Zbl 0777.00002
[40] Gallian, J.A.; Witte, D., Hamiltonian checkerboards, Math. mag., 57, 291-294, (1984) · Zbl 0549.05041
[41] Gallian, J.A.; Witte, D., When the cartesian product of two directed cycles is Hyperhamiltonian, J. graph theory, 11, 21-24, (1987) · Zbl 0612.05034
[42] H.H. Glover and T.Y. Yang, A Hamilton cycle in the Cayley graph of the (2, p, 3) presentation of PSL2(p), Discrete Math., to appear. · Zbl 0864.05061
[43] Gould, R.J.; Roth, R., Cayley digraphs and (1, j, n)-sequencings of the alternating groups an, Discrete math., 66, 91-102, (1987) · Zbl 0626.05020
[44] Holsztyński, W.; Strube, R.F.E., Paths and circuits in finite groups, Discrete math., 22, 263-272, (1978) · Zbl 0384.20022
[45] Housman, D., Enumeration of Hamiltonian paths in Cayley diagrams, Aequationes math., 23, 80-97, (1981) · Zbl 0494.05029
[46] Huang, Y., On Hamiltonian decompositions of Cayley graphs on cyclic groups, () · Zbl 0793.05068
[47] Jiang, M.; Ruskey, F., Determining the Hamilton-connectedness of certain vertex-transitive graphs, Discrete math., 133, 159-169, (1994) · Zbl 0824.05044
[48] Johnson, D., On arc-disjoint Hamiltonian circuits in a Cayley digraph of Za × zb, ()
[49] Jungreis, D., Generalized Hamiltonian circuits in the Cartesian product of two directed cycles, J. graph theory, 12, 113-120, (1988) · Zbl 0657.05033
[50] Jungreis, D., Hamiltonian paths in Cayley digraphs of finitely-generated infinite abelian groups, Discrete math., 78, 96-104, (1989) · Zbl 0702.05057
[51] D. Jungreis, Hamiltonian paths in euclidean crystallographic groups, Univ. of Minnesota, Duluth, Technical Report. · Zbl 0702.05057
[52] D. Jungreis, E. Friedman and D. Witte, Cayley graphs on groups of low order are hamiltonian, Preprint.
[53] Jungreis, I.L., Infinite Hamiltonian paths in Cayley digraphs, Discrete math., 54, 167-180, (1985) · Zbl 0569.05037
[54] Jwo, J.-S.; Lakshmivarahan, S.; Dhall, S.K., A new class of interconnection networks based on the alternating group, Networks, 23, 315-326, (1993) · Zbl 0774.90031
[55] Keating, K., Multiple-ply Hamiltonian graphs and digraphs, Ann. discrete math., 27, 81-88, (1985)
[56] Keating, K.; Witte, D., On Hamilton cycles in Cayley graphs of groups with cyclic commutator subgroup, (), 89-102
[57] Klerlein, J.B.; Starling, A.G., Hamiltonian cycles in Cayley color graphs of semi-direct products, (), 411-435
[58] Klerlein, J.B.; Starling, A.G., Hamiltonian cycles in Cayley color graphs of some special groups, (), 595-599
[59] Kompel’makher, V.L.; Liskovets, V.A., Sequential generation of arrangements by means of a basis of transpositions, Kibernetica, 3, 17-21, (1975)
[60] Kotzig, A., Every cartesian product of two circuits is decomposable into two Hamiltonian circuits, ()
[61] Lakshmivarahan, S.; Jwo, J-S.; Dhall, S.K., Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey, Parallel comput., 19, 361-407, (1993) · Zbl 0777.05064
[62] Letzter, G., Hamiltonian circuits in Cartesian products with a metacyclic factor, Ann. discrete math., 27, 103-114, (1985)
[63] D-X. Li, Hamiltonian circuits in Cayley digraph on a cyclic group, Preprint.
[64] Liu, J., Hamiltonian decompositions of Cayley graphs on abelian groups, Discrete math., 131, 163-171, (1994) · Zbl 0809.05058
[65] J. Liu, Further results on hamiltonian decompositions of Cayley graphs on abelian groups, Preprint.
[66] Llado, A.S.; Serra, O., Hamiltonian cycles in Cayley digraphs with two generators, J. combin. inform. system sci., 15, 271-280, (1990) · Zbl 0745.05029
[67] Lovász, L., Problem 11, (), 497
[68] Marušič, D., Hamiltonian circuits in Cayley graphs, Discrete math., 46, 49-54, (1983) · Zbl 0515.05042
[69] Nijenhuis, A.; Wilf, H.S., Combinatorial algorithms, (1978), Academic Press New York · Zbl 0298.05015
[70] Penn, L.E.; Witte, D., When the cartesian product of two directed cycles is Hypohamiltonian, J. graph theory, 7, 441-443, (1983) · Zbl 0523.05049
[71] Powers, D.L., Some Hamiltonian Cayley graphs, Ann. discrete math., 27, 129-140, (1985)
[72] Rankin, R.A., A campanological problem in group theory, (), 17-25 · Zbl 0030.10606
[73] Rasmussen, D.; Savage, C., Hamilton-connected derangement graphs on Sn, Discrete math., 133, 217-223, (1994) · Zbl 0808.05069
[74] V. Reiner, Personal communication.
[75] Ruskey, F.; Jiang, M.; Weston, A., On the Hamiltonicity of directed σ − τ Cayley graphs (or: a tale of backtracking, Discrete appl. math., 57, 75-83, (1995) · Zbl 0856.05063
[76] Ruskey, F.; Savage, C., Hamilton cycles that extend transposition matchings in Cayley graphs of Sn, SIAM J. disc. math., 6, 152-166, (1993) · Zbl 0771.05050
[77] Stong, R., On Hamiltonian cycles in Cayley graphs of wreath products, Discrete math., 65, 75-80, (1987) · Zbl 0623.05023
[78] Stong, R., Hamilton decompositions of Cartesian products of graphs, Discrete math., 90, 169-190, (1991) · Zbl 0746.05040
[79] Tchuente, M., Generation of permutations by graphical exchanges, Ars combin., 14, 115-122, (1982) · Zbl 0508.05041
[80] Trotter, W.T.; Erdös, P., When the cartesian product of directed cycles is Hamiltonian, J. graph theory, 2, 137-142, (1978) · Zbl 0406.05048
[81] White, A., Ringing the cosets, Amer. math. monthly, 94, 721-746, (1987) · Zbl 0632.20002
[82] Wilf, H.S., Combinatorial algorithms: an update, SIAM, cbms, 55, (1989) · Zbl 0695.05002
[83] Wilkinson, A.M., Circuits in Cayley digraphs of finite abelian groups, J. graph theory, 14, 111-116, (1990) · Zbl 0695.05024
[84] Witte, D., On Hamiltonian circuits in Cayley diagrams, Discrete math., 38, 99-108, (1982) · Zbl 0474.05036
[85] Witte, D., Cayley digraphs of prime-power order are Hamiltonian, J. combin. theory ser. B, 40, 107-112, (1986) · Zbl 0558.05024
[86] Witte, D.; Gallian, J.A., A survey: Hamiltonian cycles in Cayley graphs, Discrete math., 51, 293-304, (1984) · Zbl 0712.05039
[87] Wong, S.A., Hamilton cycles and paths in butterfly graphs, Networks, 26, 145-150, (1995) · Zbl 0855.05080
[88] Xu, M.-Y., Vertex-primitive digraphs of prime-power order are Hamiltonian, Discrete math., 128, 415-417, (1994) · Zbl 0796.05062
[89] Zhang, X.D.; Li, Z.L., Hamiltonian circuits of Cayley digraphs on a cyclic group, J. systems sci. math. sci., 10, 169-174, (1990) · Zbl 0701.05019
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.