×

Locally triangular graphs and rectagraphs with symmetry. (English) Zbl 1315.05080

Summary: Locally triangular graphs are known to be halved graphs of bipartite rectagraphs, which are connected triangle-free graphs in which every 2-arc lies in a unique quadrangle. A graph \(\Gamma\) is locally rank 3 if there exists \(G \leqslant \operatorname{Aut}(\Gamma)\) such that for each vertex \(u\), the permutation group induced by the vertex stabiliser \(G_u\) on the neighbourhood \(\Gamma(u)\) is transitive of rank 3. One natural place to seek locally rank 3 graphs is among the locally triangular graphs, where every induced neighbourhood graph is isomorphic to a triangular graph \(T_n\). This is because the graph \(T_n\), which has vertex set the 2-subsets of \(\{1, \ldots, n \}\) and edge set the pairs of 2-subsets intersecting at one point, admits a rank 3 group of automorphisms. In this paper, we classify a certain family of rectagraphs for which the permutation group induced by \(\operatorname{Aut}(\Gamma)_u\) on \(\Gamma(u)\) is 4-homogeneous for some vertex \(u\). We then use this result to classify the connected locally triangular graphs that are also locally rank 3.

MSC:

05C40 Connectivity
05C10 Planar graphs; geometric and topological aspects of graph theory

Software:

GAP; GRAPE; Magma; FinInG
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bamberg, J.; Betten, A.; Cara, P.; De Beule, J.; Lavrauw, M.; Neunhoeffer, M., FinInG - a GAP package, Version 1.0 (2013)
[2] Bosma, W.; Cannon, J.; Playoust, C., The Magma algebra system. I. The user language, J. Symbolic Comput., 24, 235-265 (1997) · Zbl 0898.68039
[3] Brouwer, A. E., On the uniqueness of a certain thin near octagon (or partial 2-geometry, or parallelism) derived from the binary Golay code, IEEE Trans. Inform. Theory, 29, 370-371 (1983) · Zbl 0505.94014
[4] Brouwer, A. E., Classification of small \((0, 2)\)-graphs, J. Combin. Theory Ser. A, 113, 1636-1645 (2006) · Zbl 1105.05009
[5] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-Regular Graphs (1989), Springer-Verlag: Springer-Verlag Berlin · Zbl 0747.05073
[6] Brouwer, A. E.; Östergård, P. R.J., Classification of the \((0, 2)\)-graphs of valency 8, Discrete Math., 309, 532-547 (2009) · Zbl 1194.05129
[7] Cameron, P. J., Suborbits in transitive permutation groups, (Combinatorics: Proceedings of the NATO Advanced Study Institute held at Nijenrode Castle. Combinatorics: Proceedings of the NATO Advanced Study Institute held at Nijenrode Castle, Breukelen, The Netherlands, 8-20 July 1974 (1975), Springer), 419-450 · Zbl 0297.20003
[8] Cameron, P. J., Permutation Groups (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1091.20002
[9] Devillers, A.; Jin, W.; Li, C. H.; Praeger, C. E., Local 2-geodesic transitivity and clique graphs, J. Combin. Theory Ser. A, 120, 500-508 (2013) · Zbl 1257.05115
[10] The GAP Group, GAP - Groups, Algorithms, and Programming, Version 4.6.3 (2013)
[11] Giudici, M.; Li, C. H.; Praeger, C. E., Analysing finite locally \(s\)-arc transitive graphs, Trans. Amer. Math. Soc., 356, 291-317 (2004) · Zbl 1022.05033
[12] Hall, J. I., Locally Petersen graphs, J. Graph Theory, 4, 173-187 (1980) · Zbl 0407.05041
[13] Hall, J. I.; Shult, E. E., Locally cotriangular graphs, Geom. Dedicata, 18, 113-159 (1985) · Zbl 0578.05058
[14] Higman, D. G., Characterization of families of rank 3 permutation groups by the subdegrees I, Arch. Math., 21, 151-156 (1970) · Zbl 0245.20003
[15] Hughes, D. R., Biplanes and semi-biplanes, (Combinatorial Mathematics, Proc. Internat. Conf. Combinatorial Theory. Combinatorial Mathematics, Proc. Internat. Conf. Combinatorial Theory, Australian Nat. Univ., Canberra, 1977. Combinatorial Mathematics, Proc. Internat. Conf. Combinatorial Theory. Combinatorial Mathematics, Proc. Internat. Conf. Combinatorial Theory, Australian Nat. Univ., Canberra, 1977, Lecture Notes in Math., vol. 686 (1978), Springer-Verlag: Springer-Verlag Berlin), 55-58 · Zbl 0418.05010
[16] Ivanov, A. A., Geometry of Sporadic Groups I, Petersen and Tilde Geometries (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0933.51006
[17] Ivanov, A. A.; Praeger, C. E., On finite affine 2-arc transitive graphs, European J. Combin., 14, 421-444 (1993) · Zbl 0794.05045
[18] Jurišić, A.; Koolen, J., 1-homogeneous graphs with cocktail party \(μ\)-graphs, J. Algebraic Combin., 18, 79-98 (2003) · Zbl 1038.05059
[19] Kantor, W. M., \(k\)-Homogeneous groups, Math. Z., 124, 261-265 (1972) · Zbl 0232.20003
[20] Leemans, D., Locally \(s\)-arc-transitive graphs related to sporadic simple groups, J. Algebra, 322, 882-892 (2009) · Zbl 1175.05067
[21] Livingstone, D.; Wagner, A., Transitivity of finite permutation groups on unordered sets, Math. Z., 90, 393-403 (1965) · Zbl 0136.28101
[22] Makhnev, A. A., On the graphs with \(μ\)-subgraphs isomorphic to \(K_{u \times 2}\), (Proc. Steklov Inst. Math., vol. 7 (2001)), S169-S178 · Zbl 1198.05130
[23] Makhnev, A. A.; Paduchikh, D. V., On locally Grassmann graphs, Dokl. Math., 76, 575-579 (2007) · Zbl 1165.05004
[24] Matsumoto, M., On the classification of locally Hamming distance-regular graphs, RIMS Kôkyûroku, 768, 50-61 (1991)
[25] Mortimer, B., The modular permutation representations of the known doubly transitive groups, Proc. Lond. Math. Soc., 41, 1-20 (1980) · Zbl 0393.20002
[26] Munemasa, A.; Pasechnik, D. V.; Shpectorov, S. V., A local characterization of the graphs of alternating forms and the graphs of quadratic forms over \(GF(2)\), (Finite Geometries and Combinatorics (1993), Cambridge University Press: Cambridge University Press Cambridge), 303-317 · Zbl 0837.05100
[27] Neumaier, A., Characterization of a class of distance regular graphs, J. Reine Angew. Math., 357, 182-192 (1985) · Zbl 0552.05042
[28] Perkel, M., On finite groups acting on polygonal graphs (1977), University of Michigan, PhD thesis
[29] Rifà, J.; Huguet, L., Classification of a class of distance-regular graphs via completely regular codes, Discrete Appl. Math., 26, 289-300 (1990) · Zbl 0687.05015
[30] Soicher, L. H., Grape - a GAP package, Version 4.3 (2012)
[31] van Bon, J., On locally \(s\)-arc transitive graphs with trivial edge kernel, Bull. Lond. Math. Soc., 43, 799-804 (2011) · Zbl 1223.05122
[32] Wild, P. R., On semibiplanes (1980), University of London, PhD thesis
[33] Wilson, R. A., The Finite Simple Groups (2009), Springer: Springer London · Zbl 1203.20012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.