×

zbMATH — the first resource for mathematics

Some problems on Cayley graphs. (English) Zbl 1148.05037
Summary: This survey paper presents the historical development of some problems on Cayley graphs which are interesting to graph and group theorists such as Hamiltonicity or diameter problems, to computer scientists and molecular biologists such as pancake problem or sorting by reversals, to coding theorists such as the vertex reconstruction problem related to error-correcting codes but not related to Ulam’s problem.

MSC:
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C45 Eulerian and Hamiltonian graphs
05C12 Distance in graphs
05E15 Combinatorial aspects of groups and algebras (MSC2010)
05-03 History of combinatorics
01A55 History of mathematics in the 19th century
01A60 History of mathematics in the 20th century
01A61 History of mathematics in the 21st century
01A65 Development of contemporary mathematics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Xu, M.Y., Some work on vertex-transitive graphs by Chinese mathematicians, (), 224-254 · Zbl 0878.05045
[2] Li, C.H., On isomorphisms of finite Cayley graphs: a survey, Discrete math., 256, 301-334, (2002) · Zbl 1018.05044
[3] Babai, L., Automorphism groups, isomorphism, reconstruction, Handbook of combinatorics, vol. 2, (1996), MIT Press Cambridge, MA, pp. 1447-1540 · Zbl 0846.05042
[4] Palmer, J.D.; Herbon, L.A., Tricircular mitochondrial genomes of brassica and raphanus: reversal of repeat configurations by inversion, sequence alignment in molecular biology, Nucleid acids res., 14, 9755-9764, (1986)
[5] Banfa, V.; Pevzner, P., Genome rearrangements and sorting by reversals, SIAM J. comput., 25, 2, 272-289, (1996) · Zbl 0844.68123
[6] Dweighter, H., E 2569 in: elementary problems and solutions, Amer. math. monthly, 82, 1, 1010, (1975)
[7] Levenshtein, V.I., New problems of graph reconstruction, Bayreuth. math. schr., 73, 246-262, (2005)
[8] E. Konstantinova, Vertex reconstruction in Cayley graphs, Discrete Math., in press. · Zbl 1182.05085
[9] Lovász, L., Problem 11 in: combinatorial structures and their applications, (), 243-246
[10] R.A. Brualdi, Report on the First IPM Conference on Algebraic Graph Theory, IPM Bull. <http://www.ipm.ac.ir/IPM/homepage/report-combinII.pdf>.
[11] Marus˘ic˘, D., Hamiltonian circuits in Cayley graphs, Discrete math., 46, 49-54, (1983) · Zbl 0515.05042
[12] McKay, B.D.; Praeger, C.E., Vertex-transitive graphs that are not Cayley graphs I, J. austal. math. soc. (ser. A), 56, 53-63, (1994) · Zbl 0795.05070
[13] McKay, B.D.; Praeger, C.E., Vertex-transitive graphs that are not Cayley graphs II, J. graph theory, 22, 4, 321-324, (1996) · Zbl 0864.05041
[14] Brouwer, A.E.; Cohen, A.M.; Neumaier, A., Distance-regular graphs, (1989), Springer-Verlag Berlin, Heidelberg · Zbl 0747.05073
[15] Björner, A.; Brenti, F., Combinatorics of Coxeter groups, (2005), Springer-Verlag Heidelberg, New York · Zbl 1110.05001
[16] Gould, R.J., Updating the Hamiltonian problem – a survey, J. graph theory, 15, 2, 121-157, (1991) · Zbl 0746.05039
[17] Rapaport-Strasser, E., Cayley color groups and Hamilton lines, Scr. math., 24, 51-58, (1959) · Zbl 0084.25401
[18] Rankin, R.A., A campanological problem in group theory II, Proc. camb. phyl. soc., 62, 11-18, (1966) · Zbl 0136.28102
[19] Lakshmivarahan, S.; Jwo, J.S.; Dhall, S.K., Symmetry in interconnection networks based on Cayley graphs of permutation groups: a survey, Parallel comput., 19, 4, 361-407, (1993) · Zbl 0777.05064
[20] Heydemann, L., Cayley graphs as interconnection networks, ()
[21] Leighton, F.T., Introduction to parallel algorithms and architectures: arrays, trees, hupercubes, (1992), Morgan Kaufman Publishers California
[22] P. Disconis, S. Holmes, Grey codes for randomization procedures, Technical Report No. 10, Dept. Statistics, Stanford University, 1994.
[23] Garey, M.R.; Johnson, D.S., Computers and intractability. A guide to the theory of NP-completeness, (1979), Freeman SF · Zbl 0411.68039
[24] Curran, S.J.; Gallian, J.A., Hamiltonian cycles and paths in Cayley graphs and digraphs – a survey, Discrete math., 156, 1-18, (1996) · Zbl 0857.05067
[25] <http://www.fmf.uni-lj.si/mohar/Problems/P6MatchingsVTGraphs.html>.
[26] Godsil, C.D.; Gutman, I., On the theory of matching polynomial, J. graph theory, 5, 137-144, (1981) · Zbl 0462.05051
[27] I. Pak, R. Radoic˘ić, Hamiltonian paths in Cayley graphs, 2004, preprint. Available from: <http://math.mit.edu/pak/hamcayley8.pdf>.
[28] Krivelevich, M.; Sudakov, B., Sparse pseudo-random graphs are Hamiltonian, J. graph theory, 42, 17-33, (2003) · Zbl 1028.05059
[29] Kompel’makher, V.L.; Liskovets, V.A., Successive generation of permutations by means of a transposition basis, Kibertetica, 3, 17-21, (1975), (in Russian)
[30] Tchuente, M., Generation of permutations by graphical exchanges, Ars combin., 14, 115-122, (1982) · Zbl 0508.05041
[31] Jwo, J.S.; Lakshmivarahan, S.; Dhall, S.K., Embedding of cycles and grids in star graphs, J. circuits syst. comput., 1, 43-74, (1991)
[32] J.S. Jwo, Analysis of interconnection networks based on Cayley graphs related to permutation groups, Ph.D. Dissertation, School of Electrical Engineering and Computer Science, University of Oklahoma, Norman, OK, 1991.
[33] Compton, R.C.; Williamson, S.G., Doubly adjacent gray codes for the symmetric group, Linear and multilinear algebra, 35, 3-4, 237-293, (1993) · Zbl 0779.94004
[34] Zaks, S., A new algorithm for generation of permutations, Bit, 24, 196-204, (1984) · Zbl 0542.68054
[35] Alspach, B.; Bermond, J.-C.; Sotteau, D., Decompositions into cycles I: Hamilton decomposition, (), 9-18 · Zbl 0713.05047
[36] Liu, J., Hamiltonian decompositions of Cayley graphs on abelian groups, Discrete math., 131, 163-171, (1994) · Zbl 0809.05058
[37] 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
[38] 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
[39] Lakshmivarahan, S.; Dhall, S.K., Analysis and design of parallel algorithms, (1990), McGraw Hill NewYork · Zbl 0593.68029
[40] Barth, D.; Raspaud, A., Two edge-disjoint Hamiltonian cycles in the butterfly graph, Inform. process. lett., 51, 175-179, (1994) · Zbl 0807.05047
[41] Wong, S.A., Hamilton cycles and paths in butterfly graphs, Network, 26, 3, 145-150, (1995) · Zbl 0855.05080
[42] Even, S.; Goldreich, O., The minimum-length generator sequence problem is NP-hard, J. algorithms, 2, 311-313, (1981) · Zbl 0467.68046
[43] Babai, L.; Kantor, W.M.; Lubotzky, A., Small diameter Cayley graphs for finite simple groups, Eur. J. combin., 10, 507-522, (1989) · Zbl 0702.05042
[44] Annexstein, F.; Baumslag, M., On the diameter and bisection size of Cayley graphs, Math. syst. theory, 26, 271-291, (1993) · Zbl 0778.05038
[45] Babai, L.; Seress, A., On the diameter of Cayley graphs of the symmetric group, J. combin. theory ser. A, 49, 1, 175-179, (1988) · Zbl 0649.20002
[46] Gates, W.H.; Papadimitriou, C.H., Bounds for sorting by prefix-reversal, Discrete math., 27, 47-57, (1979) · Zbl 0397.68062
[47] Hyedari, M.H.; Sudborough, I.H., On the diameter of the pancake network, J. algorithms, 25, 1, 67-94, (1997) · Zbl 0888.68007
[48] H. Sudborough, C. Chitturi, W. Fahle, A. Meng, L. Morales, C. Shields, W. Voit, An improved upper bound for the pancake problem, Abstract of talks at a Tribute Workshop and Festival to Honor Professor Dr. Neil D. Jones 25-26 August, 2007 Lille Auditorium Datalogisk Institut, Kobenhavns Universitet Universitetsparken 1, Kobenhavn, Denmark. <http://www.diku.dk/forskning/topps/neilfest/abstract_sudborough.html>.
[49] Cohen, D.S.; Blum, M., On the problem of sorting burnt pancakes, Discrete appl. math., 61, 2, 105-120, (1995) · Zbl 0831.68029
[50] Sankoff, D., Edit distance for genome comparison based on nonlocal operations, (), 121-135
[51] Kececioglu, J.; Sankoff, D., Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement, Algorithmica, 13, 180-210, (1995) · Zbl 0831.92014
[52] Knuth, D.E., Sorting and searching, The art of computer programming, vol. 3, (1998), Addison-Wesley Reading, Massachusetts, pp. 72, 615
[53] Bader, D.; Moret, B.M.E.; Yan, M., A linear-time algorithm for computing inversion distance between signed permutations with an experimental study, J. comput. biol., 8, 5, 483-492, (2001)
[54] Kececioglu, J.; Sankoff, D., Efficient bounds for oriented chromosome inversion distance, (), 307-325
[55] Hannenhalli, S.; Pevzner, P.A., Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals), J. ACM, 46, 1, 1-27, (1999) · Zbl 1064.92510
[56] Christie, D.A., A 3/2-approximation algorithm for sorting reversals, (), 244-252 · Zbl 0930.68044
[57] Kaplan, H.; Verbin, E., Efficient data structures and a new randomized approach for sorting signed permutations by reversals, (), 372-383
[58] Pevzner, P.A., Computational molecular biology: an algorithmic approach, (2000), The MIT Press Cambridge, MA · Zbl 0972.92011
[59] Sankoff, D.; El-Mabrouk, N., Genome rearrangement, () · Zbl 1063.68615
[60] Levenshtein, V.I., Reconstructing objects from a minimum number of distorted patterns, Dokl. acad. math., 354, 5, 593-596, (1997), (in Russian); English translation: Dokl. Math. 55 (3) (1997) 417-420 · Zbl 1008.94522
[61] Levenshtein, V.I., Efficient reconstruction of sequences, IEEE trans. inform. theory, 47, 1, 2-22, (2001) · Zbl 1029.94019
[62] E. Konstantinova, Intersection of metric balls in transposition Cayley graphs, in: Proceedings of the VII International Conference on Discrete Models in Control System Theory, Moscow, March 4-6, 2006, pp. 172-178.
[63] E. Konstantinova, V.I. Levenshtein, J. Siemons, Reconstruction of permutations distorted by single transposition errors, unpublished. <http://arxiv.org/abs/math/0702191>.
[64] Konstantinova, E., Reconstruction of permutations, Bayreuth. math. schr., 73, 213-227, (2005)
[65] Konstantinova, E., Reconstruction of permutations distorted by reversal errors, Discrete appl. math., 155, 18, 2426-2434, (2007) · Zbl 1126.05006
[66] Konstantinova, E., On reconstruction of signed permutations distorted by reversal errors, Discrete math., 308, 974-984, (2008) · Zbl 1136.05001
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.