An Algorithmic-type Classification of Tetravalent One-regular Graphs Using Computer Algebra Tools

• Autorzy: Ghasemi M.

Identyfikatory

DOI

10.3233/FI-2014-1119

• Języki publikacji: EN

Abstrakty

EN

A finite graph is one-regular if its automorphism group acts regularly on the set of its arcs. In the present paper, tetravalent one-regular graphs of order 7p²., where p is a prime, are classified using computer algebra tools.

Słowa kluczowe

EN

s-transitive graphs; symmetric graphs; Cayley graphs; magma; combinatorial algorithms

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 135, nr 3
• Strony: 211--228
• Opis fizyczny: Bibliogr. 54 poz., tab.

Twórcy

autor

Ghasemi M.

• Department of Mathematics, Urmia University, Urmia 57135, Iran

Bibliografia

• [1] Y.G. Baik, Y.Q. Feng, H.S. Sim, M.Y. Xu, On the normality of Cayley graph of abelian groups, Algebra Colloq. 5 (1998), 297–304.
• [2] N. Biggs, Algebraic Graph Theory, second ed., Cambridge University Press, Cambridge, 1993.
• [3] R. Bocian, M. Felisiak and D. Simson, Numeric and mesh algoruthms for the Coxeter spectral study of positive edge-bipartite graphs and their isotropy groups, J. Comp. Appl. Math. 2013, published online 31 July 2013, doi: 10.1016/j.cam.2013.07.013.
• [4] W. Bosma, J. Cannon, and C. Playoust, The MAGMA Algebra System I: The User Language, J. Symbolic Comput. 24 (1997) 235–265.
• [5] C.Y. Chao, On the classification of symmetric graphs with a prime number of vertices, Tran. Amer. Math. Soc. 158 (1971) 247–256.
• [6] Y. Cheng, J. Oxley, On weakly symmetric graphs of order twice a prime, J. Combin. Theory B 42 (1987) 196–211.
• [7] M. Felisiak, Computer algebra technique for Coxeter spectral of edge-bipartite graphs and matrix morsifications of Dynkin type An, Fund. Inform. 125 (2013), 21–49, doi: 10.3233/FI-2013-851.
• [8] Y.-Q. Feng, K. Kutnar, D. Marušič, C. Zhang, Tetravalent one-regular graphs of order 4p2, Filomat 28:2 (2014), 285-303.
• [9] Y.-Q. Feng, J.H. Kwak, Classifying cubic symmetric graphs of order 10p or 10p2, Science in China A 49 (2006) 300–319.
• [10] Y.-Q. Feng, J.H. Kwak, Cubic symmetric graphs of order twice an odd prime power, J. Austral. Math. Soc. 81 (2006) 153–164.
• [11] Y.-Q. Feng, J.H. Kwak, Cubic symmetric graphs of order a small number times a prime or a prime square, J. Combin. Theory B 97 (2007) 627–646.
• [12] Y.-Q. Feng, J.H. Kwak, K.S. Wang, Classifying cubic symmetric graphs of order 8p or 8p2, European J. Combin. 26 (2005) 1033–1052.
• [13] Y.Q. Feng, M.Y. Xu, Automorphism groups of teravalent Cayley graphs on regular p-groups, Discrete Math. 305 (2005), 354–360.
• [14] R. Frucht, A one-regular graph of degree three, Canad. J. Math. 4 (1952) 240–247.
• [15] A. Gardiner, C.E. Praeger, On 4-valent symmetric graphs, European. J. Combin. 15 (1994) 375–381.
• [16] A. Gardiner, C.E. Praeger, A characterization of certain families of 4-valent symmetric graphs, European. J. Combin. 15 (1994) 383–397.
• [17] M. Ghasemi, Automorphism groups of tetravalent Cayley graphs on minimal non-abelian groups, Algebra and Discrete Math. 13 (2012), 52–58.
• [18] M. Ghasemi, A classification of tetravalent one-regular graphs of order 3p2, Colloq. Math. 128 (2012) 15–23.
• [19] M. Ghasemi, R. Varmazyar, 4-valent one-regular graphs of order 5p2, accepted to Ars. Combinatoria.
• [20] M. Ghasemi, P. Spiga, 4-valent graphs of order 6p2, admitting a group of automorphisms acting regularity on arcs, Ars Math. Contemp., 9 (2015) 1–18.
• [21] M. Ghasemi, J.X. Zhou, Automorphisms of a family of cubic graphs, Algebra Colloq. 20:3 (2013), 495–506.
• [22] D. Gorenstein, Finite Simple Groups, Plenum Press, New York, 1982.
• [23] F. Harary, On the notion of balance of a signed graph, Michigan Math. 2 (1953), 143–146.
• [24] B. Huppert, An Introduction to the Theory of Finite Groups, Springer-Verlag, Berlin, 1967.
• [25] T. Inohara, Characterization of clusterability of signed graphs in terms of newcombs balance of sentiments, Applied Math and Comp. 133 (2002), 93–104.
• [26] J. Kosakowska, Lie algebras associated with quadratic forms and their applications to Ringel-Hall algebras, Algebra and Discrete Math. 4 (2008), 49–79.
• [27] J. Kosakowska, Inflation algorithms for positive and principal edge-bipartite graphs and unite quadratic forms, Fund. Inform. 119 (2012), 149-162, doi: 10.3233/FI-2012-731.
• [28] H. Kurzweil, B. Stellmacher, An introduction to the Theory of finite Groups, Erlangen, 2003.
• [29] J.H. Kwak, J.M. Oh, One-regular normal Cayley graphs on dihedral groups of valency 4 or 6 with cyclic vertex stabilizer, Acta Math. Sin. Engl. Ser. 22 (2006) 1305–1320.
• [30] P. Leszczyński and K. Stencel, Update propagator for joint scalable storage, Fund. Inform. 119(2012), 337–355, doi: 10.3233/FI-2012–741.
• [31] D. Marušič, A family of one-regular graphs of valency 4. European J. Combin. 18 (1997) 59–64.
• [32] P. Pan, L. Wang, Y. Yang, Y. Gan, L. Wang and C. Xu, Chameleon hash functions and one-time signature schemes from inner automorphism groups, Fund. Inform. 126(2013), 103–119, doi: 10.3233/FI-2013-873.
• [33] P. Potočnik, P. Spiga, G. Verret, http://www.matapp.unimib.it/ spiga/
• [34] P. Potočnik, P. Spiga, G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices, arXiv:1201.5317v1 [math.CO].
• [35] C.E. Praeger, R.J.Wang and M.Y. Xu, Symmetric graphs of order a product of two distinct primes, J. Combin. Theory Ser. B 58 (1993) 299–318.
• [36] C.E. Praeger and M.Y. Xu, Vertex-primitive graphs of order a product of two distinct primes, J. Combin. Theory Ser. B 59 (1993) 216–45.
• [37] D. Simson, Mesh algorithms for solving principal Diophantine equations, sand-glass tubes and tori of roots, Fund. Inform. 109 (2011), 425–462.
• [38] D. Simson, A framework for Coxeter spectral analysis of edge-bipartite graphs, their rational morsifications and mesh geometries of root orbits, Fund. Inform. 124 (2013), 309-338, doi: 10.3233/FI-2013-836.
• [39] D. Simson, Toroidal algorithms for mesh geometries of root orbits of the Dynkin diagram D4, Fund. Inform. 124 (2013), 339–364, doi:10.3233/FI-2013-837.
• [40] D. Simson, Algorithms determining matrix morsifications, Weyl orbits, Coxeter polynomials and mesh geometries of roots for Dynkin diagrams, Fund. Inform. 123 (2013), 447–490, doi:10.3233/FI-2013-820.
• [41] D. Simson, A Coxeter-Gram classification of simply-laced edge-bipartite graphs, SIAM J. Discr. Math. 27 (2013), 827–854 doi:10.1137/1108443721.
• [42] D. Simson and M.Wojewódzki, An algorithmic solution of a Birkhoff type problem, Fund. Inform. 83 (2008), 389–410.
• [43] C.Q. Wang and M.Y. Xu, Non-normal one-regular and tetravalent Cayley graphs of dihedral groups D2n, European J. Combin. 27 (2006) 750–766.
• [44] R.J. Wang, M.Y. Xu, A classification of symmetric graphs of order 3p, J. Combin. Theory B 58 (1993) 197–216.
• [45] C.Q. Wang and Z.Y. Zhou, Tetravalent one-regular normal Cayley graphs of dihedral groups, Acta Math. Sinica Chinese Ser. 49 (2006) 669–678.
• [46] B.H. Wehrfrtiz, A second Course in Group Theory, World Scientific, 1999.
• [47] D.B. West, Introduction to Graph Theory, Prentice Hall Inc., Upper Saddle River, NJ, 1996.
• [48] H. Wielandt, Finite Permutation Groups, Academic Press, New York, 1964.
• [49] S. Wilson, P. Potočnik, A census of edge-transitive tetravalent graphs, http://jan. ucc.nau.edu/swilson/C4Site/index.html.
• [50] M.Y. Xu, A note on one-regular graphs. Chin. Scin. Bull. 45, (2000) 2160–2162.
• [51] J. Xu, M.Y. Xu, Arc-transitive Cayley graphs of valency at most four on Abelian groups. Southest Asian Bull. Math. 25, (2001) 355–363.
• [52] M.Y. Xu, Automorphism groups and isomorphisms of Cayley digraphs, Discrete Math. 44 (2001) 1502–1508.
• [53] T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1982), 47–74.
• [54] J.-X. Zhou, Y.-Q. Feng, Tetravalent one-regular graphs of order 2pq, J. Algebraic Combin. 29 (2009) 457–471.