Magma

MAGMA Computational Algebra System

Magma
 •  How to get Magma
 •  Download
 •  Online Demo
 
Resources
 •  Online Help
 •  Discovering Mathematics with Magma
 •  Citations
 •  How to cite Magma
 •  Contributors
 •  Links
 
 •  Contact us

Combinatorics

Graph Theory

05Cxx

[1] David Abelson, Seok-Hee Hong, and D. E. Taylor. Geometric automorphism groups of graphs. Discrete Appl. Math., 155(17):2211–2226, 2007.
[2] David Abelson, Seok-Hee Hong, and Donald E. Taylor. A group-theoretic method for drawing graphs symmetrically. In Graph Drawing, volume 2528 of Lecture Notes in Comput. Sci., pages 86–97. Springer, Berlin, 2002.
[3] John Bamberg, Geoffrey Pearce, and Cheryl E. Praeger. Transitive decompositions of graph products: Rank 3 grid type. J. Group Theory, 11(2):185–228, 2008.
[4] Eiichi Bannai, Osamu Shimabukuro, and Hajime Tanaka. Finite analogues of non-Euclidean spaces and Ramanujan graphs. European J. Combin., 25(2):243–259, 2004.
[5] Eiichi Bannai, Osamu Shimabukuro, and Hajime Tanaka. Finite Euclidean graphs and Ramanujan graphs. Discrete Math., In Press, 2009.
[6] Wayne Barrett, Jason Grout, and Raphael Loewy. The minimum rank problem over the finite field of order 2: minimum rank 3. Linear Algebra and its Applications, 430(4):890 – 923, 2009.
[7] C. Bates, D. Bundy, S. Perkins, and P. Rowley. Commuting involution graphs for symmetric groups. J. Algebra, 266(1):133–153, 2003.
[8] Norman Biggs. Constructions for cubic graphs with large girth. Electron. J. Combin., 5:Article 1, 25 pp. (electronic), 1998.
[9] Mireille Boutin and Gregor Kemper. Lossless representation of graphs using distributions. arXiv:0710.1870, 19 pages, 2007.
[10] John M. Boyer and Wendy J. Myrvold. On the cutting edge: Simplified O(n) planarity by edge addition. J. Graph Algorithms Appl., 8(3):241–273 (electronic), 2004.
[11] John Bray, Christopher Parker, and Peter Rowley. Cayley type graphs and cubic graphs of large girth. Discrete Math., 214(1-3):113–121, 2000.
[12] Andries E. Brouwer, Naoyuki Horiguchi, Masaaki Kitazume, and Hiroyuki Nakasora. A construction of the sporadic Suzuki graph from U3(4). J. Combin. Theory Ser. A, 116(5):1056–1062, 2009.
[13] Pierre Cartier. Combinatorics of trees. In Surveys in modern mathematics, volume 321 of London Math. Soc. Lecture Note Ser., pages 274–282. Cambridge Univ. Press, Cambridge, 2005.
[14] Marston Conder. Constructing symmetric graphs. Theta, 3:11–16, 1989.
[15] Marston Conder. Group actions on graphs, maps and surfaces with maximum symmetry. In Groups St. Andrews 2001 in Oxford. Vol. I, volume 304 of London Math. Soc. Lecture Note Ser., pages 63–91. Cambridge Univ. Press, Cambridge, 2003.
[16] Marston Conder. Genus spectra for symmetric embeddings of graphs on surfaces. Electronic Notes in Discrete Mathematics, 31:27 – 31, 2008.
[17] Marston Conder. On symmetries of Cayley graphs and the graphs underlying regular maps. J. Algebra, 321(11):3112–3127, 2009.
[18] Marston Conder. Regular maps and hypermaps of Euler characteristic -1 to -200. Journal of Combinatorial Theory Series B, 99(2):455 – 459, 2009.
[19] Marston Conder and Peter Dobcsányi. Determination of all regular maps of small genus. J. Combin. Theory Ser. B, 81(2):224–242, 2001.
[20] Marston Conder and Peter Dobcsányi. Trivalent symmetric graphs on up to 768 vertices. J. Combin. Math. Combin. Comput., 40:41–63, 2002.
[21] Marston Conder and Brent Everitt. Regular maps on non-orientable surfaces. Geom. Dedicata, 56(2):209–219, 1995.
[22] Marston Conder, Robert Jajcay, and Thomas Tucker. Regular Cayley maps for finite abelian groups. J. Algebraic Combin., 25(3):259–283, 2007.
[23] Marston Conder and Cai Heng Li. On isomorphisms of finite Cayley graphs. European J. Combin., 19(8):911–919, 1998.
[24] Marston Conder and Peter Lorimer. Automorphism groups of symmetric graphs of valency 3. J. Combin. Theory Ser. B, 47(1):60–72, 1989.
[25] Marston Conder, Peter Lorimer, and Cheryl Praeger. Constructions for arc-transitive digraphs. J. Austral. Math. Soc. Ser. A, 59(1):61–80, 1995.
[26] Marston Conder, Aleksander Malnič, Dragan Marušič, Tomaž Pisanski, and Primož Potočnik. The edge-transitive but not vertex-transitive cubic graph on 112 vertices. J. Graph Theory, 50(1):25–42, 2005.
[27] Marston Conder, Aleksander Malnič, Dragan Marušič, and Primož Potočnik. A census of semisymmetric cubic graphs on up to 768 vertices. J. Algebraic Combin., 23(3):255–294, 2006.
[28] Marston Conder and Dragan Marušič. A tetravalent half-arc-transitive graph with non-abelian vertex stabilizer. J. Combin. Theory Ser. B, 88(1):67–76, 2003.
[29] Marston Conder, Margaret Morton, and Cheryl E. Praeger. Partition graphs for finite symmetric groups. J. Graph Theory, 25(2):107–117, 1997.
[30] Marston Conder, Margaret Morton, and Cheryl E. Praeger. Two-arc closed subsets of graphs. J. Graph Theory, 42(4):350–364, 2003.
[31] Marston Conder and Roman Nedela. Symmetric cubic graphs of small girth. J. Combin. Theory Ser. B, 97(5):757–768, 2007.
[32] Marston Conder and Roman Nedela. A refined classification of symmetric cubic graphs. J. Algebra, 322(3):722–740, 2009.
[33] Marston Conder, Primož Potočnik, and Jozef Širáň. Regular hypermaps over projective linear groups. J. Aust. Math. Soc., 85, 155–175 pages, 2008.
[34] Marston Conder, Jozef Sirán, and Tom Tucker. The genera, reflexibility and simplicity of regular maps. J. Eur. Math. Soc. (JEMS), To appear, 23 pages.
[35] Marston Conder and Cameron G. Walker. The infinitude of 7-arc-transitive graphs. J. Algebra, 208(2):619–629, 1998.
[36] Marston Conder and Steve Wilson. Inner reflectors and non-orientable regular maps. Discrete Math., 307(3-5):367–372, 2007.
[37] Maria Cristeta Cuaresma, Michael Giudici, and Cheryl E. Praeger. Homogeneous factorisations of Johnson graphs. Des. Codes Cryptogr., 46(3):303–327, 2008.
[38] Italo J. Dejter. C-homogeneous graphs via ordered pencils. arXiv:0704.2146v12 [math.CO], 18 pages, 2007.
[39] Italo J. Dejter. On Clique Turan graph-homogeneity. arXiv:0704.2146, 20 pages, 2007.
[40] Italo J. Dejter. On a {K4, K2, 2, 2}-ultrahomogeneous graph. Australas. J. Comb., 44:63–75, 2009.
[41] Alice Devillers and Michael Giudici. Involution graphs where the product of two adjacent vertices has order three. J. Aust. Math. Soc., 85(3):305–322, 2008.
[42] Alice Devillers, Michael Giudici, Cai Heng Li, and Cheryl E. Praeger. Primitive decompositions of Johnson graphs. J. Combin. Theory Ser. A, 115(6):925–966, 2008.
[43] Alice Devillers, Michael Giudici, Cai Heng Li, and Cheryl E. Praeger. Some graphs related to the small Mathieu groups. European Journal of Combinatorics, In Press, 2009.
[44] Edward Dobson and Dragan Marušič. An unusual decomposition of a complete 7-partite graph of order 28. Discrete Math., 308(20):4595–4598, 2008.
[45] Xin Gui Fang, George Havas, and Cheryl E. Praeger. On the automorphism groups of quasiprimitive almost simple graphs. J. Algebra, 222(1):271–283, 1999.
[46] Xin Gui Fang, George Havas, and Jie Wang. Automorphism groups of certain non-quasiprimitive almost simple graphs. In Groups St. Andrews 1997 in Bath, I, volume 260 of London Math. Soc. Lecture Note Ser., pages 267–274. Cambridge Univ. Press, Cambridge, 1999.
[47] Yan-Quan Feng, Klavdija Kutnar, Aleksander Malnič, and Dragan Marušič. On 2-fold covers of graphs. J. Combin. Theory Ser. B, 98(2):324–341, 2008.
[48] Yan-Quan Feng, Jin Ho Kwak, and Chuixiang Zhou. Constructing even radius tightly attached half-arc-transitive graphs of valency four. J. Algebraic Combin., 26(4):431–451, 2007.
[49] Louis Ferré and Bertrand Jouve. Vertex partitioning of a class of digraphs. Math. Sci. Hum., (158):59–77, 2002.
[50] Carla Fiori and Beatrice Ruini. Infinite classes of dihedral snarks. Mediterr. J. Math., 5(2):199–210, 2008.
[51] W. Fish, J. D. Key, and E. Mwambene. Graphs, designs and codes related to the n-cube. Discrete Math., 309(10):3255–3269, 2009.
[52] Michael Giudici, Cai Heng Li, Primož Potočnik, and Cheryl E. Praeger. Homogeneous factorisations of complete multipartite graphs. Discrete Math., 307(3-5):415–431, 2007.
[53] H. H. Glover, K. Kutnar, and Dragan Marušič. Hamiltonian cycles in cubic Cayley graphs: The <2, 4k, 3> case. J. Algebraic Combin., To appear, 2009.
[54] Jason Grout. Ultraconnected and Critical Graphs. Master of science, Brigham Young University, 2003.
[55] Paul R. Hafner. Large Cayley graphs and digraphs with small degree and diameter. In Computational Algebra and Number Theory (Sydney, 1992), volume 325 of Math. Appl., pages 291–302. Kluwer Acad. Publ., Dordrecht, 1995.
[56] Paul R. Hafner. Geometric realisation of the graphs of McKay-Miller-širáň. J. Combin. Theory Ser. B, 90(2):223–232, 2004.
[57] Paul R. Hafner. On the graphs of Hoffman-Singleton and Higman-Sims. Electron. J. Combin., 11(1):Research Paper 77, 33 pp. (electronic), 2004.
[58] Robert E. Jamison and Gretchen L. Matthews. Distance k colorings of Hamming graphs. In Proceedings of the Thirty-Seventh Southeastern International Conference on Combinatorics, Graph Theory and Computing, volume 183, pages 193–202, 2006.
[59] Peter Keevash and Benny Sudakov. Packing triangles in a graph and its complement. J. Graph Theory, 47(3):203–216, 2004.
[60] István Kovács, Aleksander Malnič, Dragan Marušič, and Štefko Miklavič. One-matching bi-Cayley graphs over abelian groups. European J. Combin., 30(2):602–616, 2009.
[61] K. Kutnar, Aleksander Malnič, Dragan Marušič, and Štefko Miklavič. The strongly distance-balanced property of the generalized Petersen graphs. Ars Math. Contemp., 2(1):41–47, 2009.
[62] Klavdija Kutnar, Aleksander Malnič, Dragan Marušič, and Štefko Miklavič. Distance-balanced graphs: Symmetry conditions. Discrete Math., 306(16):1881–1894, 2006.
[63] Klavdija Kutnar and Dragan Marušič. Hamiltonicity of vertex-transitive graphs of order 4p. European J. Combin., 29(2):423–438, 2008.
[64] Klavdija Kutnar and Dragan Marušič. A complete classification of cubic symmetric graphs of girth 6. J. Combin. Theory Ser. B, 99(1):162–184, 2009.
[65] Klavdija Kutnar and Primož Šparl. Hamilton paths and cycles in vertex-transitive graphs of order 6p. Discrete Mathematics, To appear, 2009.
[66] Felix Lazebnik and Raymond Viglione. An infinite series of regular edge- but not vertex-transitive graphs. J. Graph Theory, 41(4):249–258, 2002.
[67] Dimitri Leemans. Locally s-arc-transitive graphs related to sporadic simple groups. J. Algebra, 322(3):882–892, 2009.
[68] Cai Heng Li, Tian Khoon Lim, and Cheryl E. Praeger. Homogeneous factorisations of complete graphs with edge-transitive factors. J. Algebraic Combin., 29(1):107–132, 2009.
[69] Paulette Lieby. Colouring planar graphs. In Discovering Mathematics with Magma, volume 19 of Algorithms Comput. Math., pages 315–330. Springer, Berlin, 2006.
[70] Tian Khoon Lim. Edge-transitive homogeneous factorisations of complete graphs. arXiv:math.CO/0605253, 130 pages, 2004.
[71] Tian Khoon Lim. Arc-transitive homogeneous factorizations and affine planes. J. Combin. Des., 14(4):290–300, 2006.
[72] Tian Khoon Lim and Cheryl E. Praeger. On generalized Paley graphs and their automorphism groups. Michigan Math. J., 58(1):293–308, 2009.
[73] Marko Lovrečič Saražin, Walter Pacco, and Andrea Previtali. Generalizing the generalized Petersen graphs. Discrete Math., 307(3-5):534–543, 2007.
[74] Aleksander Malnič, Dragan Marušič, Štefko Miklavič, and Primož Potočnik. Semisymmetric elementary abelian covers of the Möbius-Kantor graph. Discrete Math., 307(17-18):2156–2175, 2007.
[75] Aleksander Malnič, Dragan Marušič, and Primož Potočnik. Elementary abelian covers of graphs. J. Algebraic Combin., 20(1):71–97, 2004.
[76] Aleksander Malnič, Dragan Marušič, and Primož Potočnik. On cubic graphs admitting an edge-transitive solvable group. J. Algebraic Combin., 20(1):99–113, 2004.
[77] Aleksander Malnič, Dragan Marušič, and Primož Šparl. On strongly regular bicirculants. European J. Combin., 28(3):891–900, 2007.
[78] Aleksander Malnič and Primož Potočnik. Invariant subspaces, duality, and covers of the Petersen graph. European J. Combin., 27(6):971–989, 2006.
[79] Dragan Marušič. On 2-arc-transitivity of Cayley graphs. J. Combin. Theory Ser. B, 87(1):162–196, 2003.
[80] Dragan Marušič and Primož Potočnik. Bridging semisymmetric and half-arc-transitive actions on graphs. European J. Combin., 23(6):719–732, 2002.
[81] Margaret Morton. A note on arc-transitive circulants. Bull. Inst. Combin. Appl., 23:63–68, 1998.
[82] Ju-Mok Oh. Arc-transitive elementary abelian covers of the Pappus graph. Discrete Math., In Press, 2009.
[83] Ju-Mok Oh. A classification of cubic s-regular graphs of order 14p. Discrete Math., 309(9):2721–2726, 2009.
[84] Ju-Mok Oh. A classification of cubic s-regular graphs of order 16p. Discrete Math., 309(10):3150–3155, 2009.
[85] Alen Orbanić. Parallel-product decomposition of edge-transitive maps. arXiv:math.CO/0510428, 30 pages, 2005.
[86] Michael E. O'Sullivan. Algebraic construction of sparse matrices with large girth. IEEE Trans. Inform. Theory, 52(2):718–727, 2006.
[87] C. W. Parker. Semisymmetric cubic graphs of twice odd order. European J. Combin., 28(2):572–591, 2007.
[88] Christopher Parker and Peter Rowley. Ω-covers of graphs. Bull. London Math. Soc., 32(6):658–662, 2000.
[89] Christopher Parker and Peter Rowley. Subgroup-chain graphs. Graphs Combin., 19(4):537–545, 2003.
[90] Manley Perkel and Cheryl E. Praeger. Polygonal graphs: New families and an approach to their analysis. In Proceedings of the Twenty-eighth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1997), volume 124, pages 161–173, 1997.
[91] Manley Perkel, Cheryl E. Praeger, and Richard Weiss. On narrow hexagonal graphs with a 3-homogeneous suborbit. J. Algebraic Combin., 13(3):257–273, 2001.
[92] Adolfo Piperno. Search space contraction in canonical labeling of graphs (preliminary version). arXiv:0804.4881, 2008.
[93] Primož Potočnik. A list of 4-valent 2-arc-transitive graphs and finite faithful amalgams of index (4, 2). European J. Combin., 30(5):1323–1336, 2009.
[94] Cheryl E. Praeger and Leonard H. Soicher. Low Rank Representations and Graphs for Sporadic Groups, volume 8 of Australian Mathematical Society Lecture Series. Cambridge University Press, Cambridge, 1997.
[95] Yin Tan, Alexander Pott, and Tao Feng. Strongly regular graphs associated with ternary bent functions. Journal of Combinatorial Theory, Series A, In Press, 2009.
[96] Nicolas M. Thiéry. Algebraic invariants of graphs; A study based on computer exploration. SIGSAM Bulletin, 34(3):9–20, 2000.
[97] Libero Verardi. Matrices, graphs and equivalence relations. Ann. Mat. Pura Appl. (4), 180(4):413–428, 2002.
[98] Xiuyun Wang and Yan-Quan Feng. Hexavalent half-arc-transitive graphs of order 4p. European J. Combin., 30(5):1263–1270, 2009.
[99] Yan Wang, Xin Gui Fang, and D. F. Hsu. On the edge-forwarding indices of Frobenius graphs. Acta Math. Sin. (Engl. Ser.), 22(6):1735–1744, 2006.
[100] Doug Wiedemann and Michael Zieve. Equivalence of sparse circulants: The bipartite Adam problem. arXiv:0706.1567, 20 pages, 2007.
[101] Cui Zhang, Jin-Xin Zhou, and Yan-Quan Feng. Automorphisms of cubic Cayley graphs of order 2pq. Discrete Math., 309(9):2687–2695, 2009.
[102] Jin-Xin Zhou. Tetravalent s-transitive graphs of order 4p. Discrete Math., In Press, 2009.
[103] Jin-Xin Zhou and Yan-Quan Feng. Tetravalent one-regular graphs of order 2pq. J. Algebraic Combin., 29(4):457–471, 2009.

Prev: Designs and Configurations Up: Combinatorics Next: Extremal Combinatorics

Valid HTML 4.01! Valid CSS!