Coverings of Graphs and Maps, Orthogonality, and Eigenvectors
Jozef Širáň
Slovak University of Technology Department of Mathematics, SvF 813 68 Bratislava Slovakia
DOI: 10.1023/A:1011218020755
Abstract
Lifts of graph and map automorphisms can be described in terms of voltage assignments that are, in a sense, compatible with the automorphisms. We show that compatibility of ordinary voltage assignments in Abelian groups is related to orthogonality in certain Z \mathcal{Z} -modules. For cyclic groups, compatibility turns out to be equivalent with the existence of eigenvectors of certain matrices that are naturally associated with graph automorphisms. This allows for a great simplification in characterizing compatible voltage assignments and has applications in constructions of highly symmetric graphs and maps.
Pages: 57–72
Keywords: graph; map; covering; voltage assignment; orthogonality; eigenvectors; automorphism
Full Text: PDF
References
1. D. Archdeacon, “The medial graph and voltage-current duality,” Discrete Math. 104 (1992), 111-141.
2. D. Archdeacon, B. Richter, J. \check Sirá\?n, and M. \check Skoviera, “Branched coverings of maps and lifts of map homomorphisms,” Australas. J. Combinat. 9 (1994), 109-121.
3. D. Archdeacon, J. \check Sirá\check n, and M. \check Skoviera, “Self-dual regular maps from medial graphs,” Acta Math. Univ. Comenianae LXI (1992), 57-64.
4. N.L. Biggs, “Homological coverings of graphs,” J. London Math. Soc. 30 (1984), 1-14.
5. J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, American Elsevier, New York, 1976.
6. D. \check Z. Djokovic, “Automorphisms of graphs and coverings,” J. Combinat. Theory Ser. B 16 (1974), 243-247.
7. J.L. Gross and T.W. Tucker, Topological Graph Theory, Wiley-Interscience, New York, 1987.
8. P. Gvozdjak and J. \check Sirá\check n, “Regular maps from voltage assignments,” in Graph Structure Theory, N. Robertson and P. Seymour (Eds.), Contemporary Mathematics (AMS Series), Vol. 147, 1993, pp. 441-454.
9. G.A. Jones, “Maps on surfaces and Galois groups,” Math. Slovaca 47 (1997), 1-33.
10. G.A. Jones and D. Singerman, “Theory of maps on orientable surfaces,” Proc. London Math. Soc. 37(3) (1978), 273-307.
11. G.A. Jones and D. Singerman, “Bely\check ı functions, hypermaps, and Galois groups,” Bull. London Math. Soc. 28 (1996), 561-590.
12. J.H. Kwak and J. Lee, “Isomorphism classes of M graph bundles,” Canad. J. Math. XLII (1990), 747-761.M
13. A. Malni\check c, R. Nedela, and M. \check Skoviera, “Lifting graph automorphisms by voltage assignments,” Europ. J. Combin. 21 (2000), 927-947.
14. W.S. Massey, Algebraic Topology: An Introduction, Harcourt Brace and World, New York, 1967.
15. R.B. Richter, J. \check Sirá\check n, R. Jajcay, T.W. Tucker, and M.E. Watkins, “Cayley maps,” submitted.
16. R.B. Richter and W.P. Wardlaw, “Diagonalization over commutative rings,” Amer. Math. Monthly 97 (1990), 223-227.
17. D.B. Surowski, “Lifting map automorphisms and MacBeath's theorem,” J. Combinat. Theory Ser. B 50 (1988), 135-149.
2. D. Archdeacon, B. Richter, J. \check Sirá\?n, and M. \check Skoviera, “Branched coverings of maps and lifts of map homomorphisms,” Australas. J. Combinat. 9 (1994), 109-121.
3. D. Archdeacon, J. \check Sirá\check n, and M. \check Skoviera, “Self-dual regular maps from medial graphs,” Acta Math. Univ. Comenianae LXI (1992), 57-64.
4. N.L. Biggs, “Homological coverings of graphs,” J. London Math. Soc. 30 (1984), 1-14.
5. J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, American Elsevier, New York, 1976.
6. D. \check Z. Djokovic, “Automorphisms of graphs and coverings,” J. Combinat. Theory Ser. B 16 (1974), 243-247.
7. J.L. Gross and T.W. Tucker, Topological Graph Theory, Wiley-Interscience, New York, 1987.
8. P. Gvozdjak and J. \check Sirá\check n, “Regular maps from voltage assignments,” in Graph Structure Theory, N. Robertson and P. Seymour (Eds.), Contemporary Mathematics (AMS Series), Vol. 147, 1993, pp. 441-454.
9. G.A. Jones, “Maps on surfaces and Galois groups,” Math. Slovaca 47 (1997), 1-33.
10. G.A. Jones and D. Singerman, “Theory of maps on orientable surfaces,” Proc. London Math. Soc. 37(3) (1978), 273-307.
11. G.A. Jones and D. Singerman, “Bely\check ı functions, hypermaps, and Galois groups,” Bull. London Math. Soc. 28 (1996), 561-590.
12. J.H. Kwak and J. Lee, “Isomorphism classes of M graph bundles,” Canad. J. Math. XLII (1990), 747-761.M
13. A. Malni\check c, R. Nedela, and M. \check Skoviera, “Lifting graph automorphisms by voltage assignments,” Europ. J. Combin. 21 (2000), 927-947.
14. W.S. Massey, Algebraic Topology: An Introduction, Harcourt Brace and World, New York, 1967.
15. R.B. Richter, J. \check Sirá\check n, R. Jajcay, T.W. Tucker, and M.E. Watkins, “Cayley maps,” submitted.
16. R.B. Richter and W.P. Wardlaw, “Diagonalization over commutative rings,” Amer. Math. Monthly 97 (1990), 223-227.
17. D.B. Surowski, “Lifting map automorphisms and MacBeath's theorem,” J. Combinat. Theory Ser. B 50 (1988), 135-149.