Elementary Abelian Covers of Graphs
Aleksander Malnič
, Dragan Marušič
and Primož Potočnik
DOI: 10.1023/B:JACO.0000047294.42633.25
Abstract
Let C {\mathcal{C}} G ( X) be the set of all (equivalence classes of) regular covering projections of a given connected graph X along which a given group G C {\mathcal{C}} G ( X), where C {\mathcal{C}} G ( N {\mathcal{N}} G ( C {\mathcal{C}} G p ( X) C {\mathcal{C}} G ( X) denote the sublattice of all regular covering projections with an elementary abelian p-group of covering transformations. There is an algorithm which explicitly constructs C {\mathcal{C}} G p ( X) in the sense that, for each member of C {\mathcal{C}} G p ( X), a concrete voltage assignment on X which determines this covering up to equivalence, is generated. The algorithm uses the well known algebraic tools for finding invariant subspaces of a given linear representation of a group. To illustrate the method two nontrival examples are included.
Pages: 71–97
Keywords: covering projection; lifting automorphisms; Cayley voltages; homological covering; invariant subspace; lattice; arc-transitive graph; semisymmetric graph; dipole; heawood graph
Full Text: PDF
References
1. N.L. Biggs, “Homological coverings of graphs,” J. London Math. Soc. 30 (1984), 1-14.
2. W. Bosma, C. Cannon, and C. Playoust, “The MAGMA algebra system I: The user language,” J. Symbolic Comput. 24 (1997), 235--265.
3. M.D.E. Conder, A. Malni\check c, D. Maru\check si\check c, T. Pisanski, and P. Poto\check cnik, “The edgebut not vertex-transitive cubic graph on 112 vertices,” J. Graph Theory, to appear.
4. M.D.E. Conder, A. Malni\check c, D. Maru\check si\check c, and P. Poto\check cnik, “A census of cubic semisymmetric graphs on up to 768 vertices,” submitted.
5. D. \check Z. Djokovi\check c, “Automorphisms of graphs and coverings,” J. Combin. Theory Ser. B 16 (1974), 243--247.
6. S.F. Du, J.H. Kwak, and M.Y. Xu, “Lifting of automorphisms on the elementary abelian regular coverings,” Lin. Alg. Appl. 373 (2003), 101--119.
7. S.F. Du, J.H. Kwak, and M.Y. Xu, “On 2-arc transitive covers of complete graphs with covering transformation group Z3p,” J. Combin. Theory Ser. B, to appear.
8. R.Q. Feng and J.H. Kwak, “Typical circulant double coverings of a circulant graph,” Discrete Math. 277 (2004), 73-85.
9. Y.Q. Feng and J.H. Kwak, “s-regular cubic graphs as coverings of the complete bipartite graph K3,3,” J. Graph Theory 45 (2004), 101-112.
10. C.D. Godsil and G. Royle, Algebraic Graph Theory, Springer-Verlag, New York, 2001.
11. J.L. Gross and T.W. Tucker, Topological Graph Theory, Wiley-Interscience, New York, 1987.
12. M. Hofmeister, “Graph covering projections arising from finite vector spaces over finite fields,” Discrete Math. 143 (1995), 87-97.
13. D.F. Holt and S. Rees, “Testing modules for irreducibility,” J. Austral. Math. Soc. Ser. A 57 (1994), 1-16.
14. N. Jacobson, Lectures in Abstract Algebra, II. Linear Algebra, Springer-Verlag, New York, 1953.
15. R. Lidl and H. Niederreiter, Finite Fields in Encyclopedia of Mathemaics and Applications, Cambridge Univ. Press, 1984.
16. A. Malni\check c, D. Maru\check si\check c, and P. Poto\check cnik, “On cubic graphs admitting an edge-transitive solvable group,” J. Alg. Combin. 20 (2004), 155-169.
17. A. Malni\check c, D. Maru\check si\check c, P. Poto\check cnik, and C.Q. Wang, “An infinite family of cubic edgebut not vertex-transitive graphs,” Discrete Math. 280 (2004), 133-148.
18. A. Malni\check c, R. Nedela, and M. \check Skoviera, “Lifting graph automorphisms by voltage assignments,” Europ. J. Combin. 21 (2000), 927-947.
19. P.M. Neumann and C.E. Praeger, “Cyclic matrices and the Meataxe,” in Groups and computation, III (Columbus, OH, 1999), 291--300, Ohio State Univ. Math. Res. Inst. Publ., 8, de Gruyter, Berlin, 2001.
20. M. Sch\ddot onert et al., GAP-Groups, Algorithms, and Programming, Lehrstuhl D fur Mathematik, RWTH, Aachen, 1994.
21. D.B. Surowski and C.W. Schroeder, “Homological methods in algebraic map theory,” Europ. J. Combin. 24 (2003), 1003-1044.
22. J. \check Sirá\check n, “Coverings of graphs and maps, orthogonality, and eigenvectors,” J. Alg. Combin. 14 (2001), 57- 72.
23. M. \check Skoviera, “A contribution to the theory of voltage graphs,” Discrete Math. 61 (1986), 281-292.
24. A. Venkatesh, Covers in imprimitively symmetric graphs, Honours dissertation, Department of Mathematics, University of Western Australia, 1997.
25. A. Venkatesh, “Graph coverings and group liftings,” manuscript.
26. S. Wilson, “A worthy family of semisymmetric graphs,” Discrete Math. 271 (2003), 283-294.
2. W. Bosma, C. Cannon, and C. Playoust, “The MAGMA algebra system I: The user language,” J. Symbolic Comput. 24 (1997), 235--265.
3. M.D.E. Conder, A. Malni\check c, D. Maru\check si\check c, T. Pisanski, and P. Poto\check cnik, “The edgebut not vertex-transitive cubic graph on 112 vertices,” J. Graph Theory, to appear.
4. M.D.E. Conder, A. Malni\check c, D. Maru\check si\check c, and P. Poto\check cnik, “A census of cubic semisymmetric graphs on up to 768 vertices,” submitted.
5. D. \check Z. Djokovi\check c, “Automorphisms of graphs and coverings,” J. Combin. Theory Ser. B 16 (1974), 243--247.
6. S.F. Du, J.H. Kwak, and M.Y. Xu, “Lifting of automorphisms on the elementary abelian regular coverings,” Lin. Alg. Appl. 373 (2003), 101--119.
7. S.F. Du, J.H. Kwak, and M.Y. Xu, “On 2-arc transitive covers of complete graphs with covering transformation group Z3p,” J. Combin. Theory Ser. B, to appear.
8. R.Q. Feng and J.H. Kwak, “Typical circulant double coverings of a circulant graph,” Discrete Math. 277 (2004), 73-85.
9. Y.Q. Feng and J.H. Kwak, “s-regular cubic graphs as coverings of the complete bipartite graph K3,3,” J. Graph Theory 45 (2004), 101-112.
10. C.D. Godsil and G. Royle, Algebraic Graph Theory, Springer-Verlag, New York, 2001.
11. J.L. Gross and T.W. Tucker, Topological Graph Theory, Wiley-Interscience, New York, 1987.
12. M. Hofmeister, “Graph covering projections arising from finite vector spaces over finite fields,” Discrete Math. 143 (1995), 87-97.
13. D.F. Holt and S. Rees, “Testing modules for irreducibility,” J. Austral. Math. Soc. Ser. A 57 (1994), 1-16.
14. N. Jacobson, Lectures in Abstract Algebra, II. Linear Algebra, Springer-Verlag, New York, 1953.
15. R. Lidl and H. Niederreiter, Finite Fields in Encyclopedia of Mathemaics and Applications, Cambridge Univ. Press, 1984.
16. A. Malni\check c, D. Maru\check si\check c, and P. Poto\check cnik, “On cubic graphs admitting an edge-transitive solvable group,” J. Alg. Combin. 20 (2004), 155-169.
17. A. Malni\check c, D. Maru\check si\check c, P. Poto\check cnik, and C.Q. Wang, “An infinite family of cubic edgebut not vertex-transitive graphs,” Discrete Math. 280 (2004), 133-148.
18. A. Malni\check c, R. Nedela, and M. \check Skoviera, “Lifting graph automorphisms by voltage assignments,” Europ. J. Combin. 21 (2000), 927-947.
19. P.M. Neumann and C.E. Praeger, “Cyclic matrices and the Meataxe,” in Groups and computation, III (Columbus, OH, 1999), 291--300, Ohio State Univ. Math. Res. Inst. Publ., 8, de Gruyter, Berlin, 2001.
20. M. Sch\ddot onert et al., GAP-Groups, Algorithms, and Programming, Lehrstuhl D fur Mathematik, RWTH, Aachen, 1994.
21. D.B. Surowski and C.W. Schroeder, “Homological methods in algebraic map theory,” Europ. J. Combin. 24 (2003), 1003-1044.
22. J. \check Sirá\check n, “Coverings of graphs and maps, orthogonality, and eigenvectors,” J. Alg. Combin. 14 (2001), 57- 72.
23. M. \check Skoviera, “A contribution to the theory of voltage graphs,” Discrete Math. 61 (1986), 281-292.
24. A. Venkatesh, Covers in imprimitively symmetric graphs, Honours dissertation, Department of Mathematics, University of Western Australia, 1997.
25. A. Venkatesh, “Graph coverings and group liftings,” manuscript.
26. S. Wilson, “A worthy family of semisymmetric graphs,” Discrete Math. 271 (2003), 283-294.