Vertex reconstruction in Cayley graphs. (English) Zbl 1182.05085
Summary: We review recent results on the vertex reconstruction problem (which is not related to Ulam’s problem) in Cayley graphs. The problem of reconstructing an arbitrary vertex \(x\) from its \(r\)-neighbors, that are, vertices at distance at most \(r\) from \(x\), consists of finding the minimum restrictions on the number of \(r\)-neighbors when such a reconstruction is possible. We discuss general results for simple, regular and Cayley graphs. To solve this problem for given Cayley graphs, it is essential to investigate their structural and combinatorial properties. We present such properties for Cayley graphs on the symmetric group Sym\(_n\) and the hyperoctahedral group B\(_n\) (the group of signed permutations) and overview the main results for them. The choice of generating sets for these graphs is motivated by applications in coding theory, computer science, molecular biology and physics.
MSC:
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
Keywords:
vertex reconstruction problem; Cayley graphs; the symmetric group; the hyperoctahedral group; signed permutations; sorting by reversals; pancake problemReferences:
| [1] | Akers, S. B.; Krishnamurthy, B., A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, 4, 555-566 (1989) · Zbl 0678.94026 |
| [2] | Annexstein, F.; Baumslag, M., On the diameter and bisection size of Cayley graphs, Math. System Theory, 26, 271-291 (1993) · Zbl 0778.05038 |
| [3] | Babai, L.; Kantor, W. M.; Lubotzky, A., Small diameter Cayley graphs for finite simple groups, European J. Combin., 10, 507-522 (1989) · Zbl 0702.05042 |
| [4] | 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 |
| [5] | Banfa, V.; Pevzner, P. A., Genome rearrangments and sorting by reversals, SIAM J. Comput., 25, 2, 272-289 (1996) · Zbl 0844.68123 |
| [6] | Björner, A.; Brenti, F., Combinatorics of Coxeter Groups (2005), Springer Verlag: Springer Verlag Heidelberg, New York · Zbl 1110.05001 |
| [7] | Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-Regular Graphs (1989), Springer-Verlag: Springer-Verlag Berlin, Heidelberg · Zbl 0747.05073 |
| [8] | Cohen, D. S.; Blum, M., On the problem of sorting burnt pancakes, Discrete Appl. Math., 61, 2, 105-120 (1995) · Zbl 0831.68029 |
| [9] | Conway, J. H.; Sloane, N. J.A., Sphere Packings, Lattices and Groups (1988), Springer-Verlag: Springer-Verlag New York, Berlin · Zbl 0634.52002 |
| [10] | Chen, T.; Skiena, S. S., Sorting with fixed-length reversals, Discrete Appl. Math., 71, 1, 269-295 (1996) · Zbl 0870.68052 |
| [11] | Dweighter, H., E 2569, Elementary Problems and Solutions. Elementary Problems and Solutions, Amer. Math. Monthly, 82, 1, 1010 (1975) |
| [12] | Even, S.; Goldreich, O., The minimum-length generator sequence problem is \(N P\)-hard, J. Algorithms, 2, 3, 311-313 (1981) · Zbl 0467.68046 |
| [13] | Fragopoulou, P.; Akl, S. G., Optimal communication algorithms on star graphs using spanning tree constructions, J. Parallel Distrib. Comput., 24, 1, 55-71 (1995) |
| [14] | Gates, W. H.; Papadimitriou, C. H., Bounds for sorting by prefix-reversal, Discrete Math., 27, 47-57 (1979) · Zbl 0397.68062 |
| [15] | Gu, Q.-P.; Peng, S., Fault tolerant routing in hypercubes and star graphs, Parallel Process. Lett., 6, 1, 127-136 (1996) |
| [16] | Heydemann, L., Cayley graphs as interconnection networks, (Hahn, G.; Sabidussi, G., Graph Symmetry: Algebraic Methods and Applications (1997), Kluwer: Kluwer Amsterdam) |
| [17] | Hyedari, M. H.; Sudborough, I. H., On the diameter of the pancake network, J. Algorithms, 25, 1, 67-94 (1997) · Zbl 0888.68007 |
| [18] | Knuth, D. E., (Sorting and Searching. Sorting and Searching, The Art of Computer Programming, vol. 3 (1998), Addison-Wesley: Addison-Wesley Reading, MA) |
| [19] | Konstantinova, E., Reconstruction of permutations, Bayreuther Math. Schriften, 73, 213-227 (2005) |
| [20] | 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; 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 |
| [21] | Konstantinova, E., Reconstruction of permutations distorted by reversal errors, Discrete Appl. Math., 155, 18, 2426-2434 (2007) · Zbl 1126.05006 |
| [22] | Konstantinova, E., On reconstruction of signed permutations distorted by reversal errors, Discrete Math., 308, 974-984 (2008) · Zbl 1136.05001 |
| [23] | 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 |
| [24] | 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 |
| [25] | Levenshtein, V. I., Efficient reconstruction of sequences, IEEE Trans. Inform. Theory, 47, 1, 2-22 (2001) · Zbl 1029.94019 |
| [26] | Levenshtein, V. I., New problems of graph reconstruction, Bayreuther Math. Schriften, 73, 246-262 (2005) |
| [27] | Schibell, S. T.; Stafford, S. M., Processor interconnection networks from Cayley graphs, Discrete Appl. Math., 40, 3, 333-357 (1992) · Zbl 0782.68014 |
| [28] | 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. See: http://www.diku.dk/forskning/topps/neilfest/abstract_sudborough.html; 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. See: http://www.diku.dk/forskning/topps/neilfest/abstract_sudborough.html |
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.
