<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Trivalent 2-Arc Transitive Graphs of Type G21 are Near Polygonal
Sanming Zhou
Department of Mathematics and Statistics, The University of Melbourne, Parkville, VIC 3010, Australia
Annals of Combinatorics 14 (3) pp.397-405 September, 2010
AMS Subject Classification: 05C25, 20B25
A connected graph ∑ of girth at least four is called a near n-gonal graph with respect to E, where n ≥ 4 is an integer, if E is a set of n-cycles of ∑ such that every path of length two is contained in a unique member of E.It is well known that connected trivalent symmetric graphs can be classified into seven types. In this note we prove that every connected trivalent G-symmetric graph ∑≠ K4 of type G21 is a near polygonal graph with respect to two G-orbits on cycles of ∑. Moreover, we give an algorithm for constructing the unique cycle in each of these $G$-orbits containing a given path of length two.
Keywords: symmetric graph; arc-transitive graph; trivalent symmetric graph; near polygonal graph; three-arc graph


1. Biggs, N.L.: Algebraic Graph Theory, second edition. Cambridge University Press, Cambridge (1993)

2. Conder, M., Dobcsányi, P.: Trivalent symmetric graphs on up to 768 vertices. J. Combin. Math. Combin. Comput. 40(1), 41--63 (2002)

3. Conder, M., Lorimer, P.: Automorphism groups of symmetric graphs of valency 3. J. Combin. Theory Ser. B 47(1), 60--72 (1989)

4. Coxeter, H.S.M., Moser, W.O.J.: Generators and Relations for Discrete Groups. Springer-Verlag, Berlin-Göttingen-Heidelberg (1957)

5. Djokovic, D.Z., Miller, G.L.: Regular groups of automorphisms of cubic graphs. J. Combin. Theory Ser. B 29(2), 195--230 (1980)

6. Dixon, J.D., Mortimer, B.: Permutation Groups. Springer, New York (1996)

7. Li, C.H., Praeger, C.E., Zhou, S.: A class of finite symmetric graphs with 2-arc transitive quotients. Math. Proc. Cambridge Philos. Soc. 129(1), 19--34 (2000)

8. Perkel, M.: Bounding the valency of polygonal graphs with odd girth. Canad. J. Math. 31(6), 1307--1321 (1979)

9. Perkel, M.: Near-polygonal graphs. Ars Combin. 26A, 149--170 (1988)

10. Perkel, M., Praeger, C.E.: Polygonal graphs: new families and an approach to their analysis. Congr. Numer. 124, 161--173 (1997)

11. Perkel, M., Praeger, C.E.: On narrow hexagonal graphs with a 3-homogenous suborbit. J. Algebraic Combin. 13(3), 257--273 (2001)

12. Praeger, C.E., Li, C.H., Niemeyer, A.C.: Finite transitive permutation groups and finite vertex transitive graphs. In: Hahn, G., Sabidussi, G. (eds.) Graph Symmetry, pp. 277--318. Kluwer Academic Publishing, Dordrecht (1997)

13. Tutte, W.T.: A family of cubical graphs. Proc. Cambridge Philos. Soc. 43, 459--474 (1947)

14. Zhou, S.: Almost covers of $2$-arc transitive graphs. Combinatorica 24(4), 731--745 (2004) [Erratum: 27(6), 745--746 (2007)]

15. Zhou, S.: Imprimitive symmetric graphs, 3-arc graphs and 1-designs. Discrete Math. 244(1-3), 521--537 (2002)

16. Zhou, S.: Two-arc transitive near polygonal graphs. In: Bondy, J.A. et al (eds.) Graph Theory in Paris, pp. 375--380. Birkhäuser Verlag, Basel/Switzerland (2006)

17. Zhou, S.: On a class of finite symmetric graphs. European J. Combin. 29(3), 630--640 (2008)