×

zbMATH — the first resource for mathematics

Geometric realisation of the graphs of McKay-Miller-Širáň. (English) Zbl 1043.05060
This paper provides an alternative construction of three families of graphs of diameter 2 and order \(2q^2\), where \(q\) is a prime power. Some of the largest known graphs of diameter 2 come from these families which have originally been constructed by McKay, Miller and Širáň. In this paper the graphs are described as modified incidence graphs of an affine plane. This description allows the complete determination of the automorphism groups of the graphs.

MSC:
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C62 Graph representations (geometric and intersection representations, etc.)
Software:
nauty; Magma
PDF BibTeX Cite
Full Text: DOI
References:
[1] Bosma, W.; Cannon, J.J., Handbook of magma functions, (1996), University of Sydney Sydney
[2] F. Comellas, The (degree, diameter) problem for graphs, http://www-mat.upc.es/grup_de_grafs/grafs/taula_delta_d.html. · Zbl 0843.05033
[3] Cronheim, A., T-groups and their geometry, Illinois J. math., 9, 1-30, (1965) · Zbl 0137.14601
[4] Dembowski, P., Finite geometries, (1968), Springer Berlin · Zbl 0159.50001
[5] M.J. Dinneen, Group-theoretic methods for designing networks, http://www.cs.auckland.ac.nz/CDMTCS/researchreports/082nznews.pdf. · Zbl 0901.68151
[6] Fan, C.; Schwenk, A.J., Structure of the hoffman – singleton graph, Congr. numer., 94, 3-8, (1993) · Zbl 0801.05037
[7] Godsil, C.D., Algebraic combinatorics, (1993), Chapman & Hall New York · Zbl 0814.05075
[8] Hafner, P.R., The hoffman – singleton graph and its automorphisms, J. algebraic combin., 18, 7-12, (2003) · Zbl 1021.05046
[9] James, L.O., A combinatorial proof that the Moore (7,2) graph is unique, Utilitas math., 5, 79-84, (1974) · Zbl 0279.05117
[10] Jungnickel, D., Divisible semiplanes, arcs, and relative difference sets, Canad. J. math., 39, 4, 1001-1024, (1987) · Zbl 0637.05011
[11] McKay, B.D., Nauty User’s guide (version 1.5), technical report TR-CS-90-002, department of computer science, (1990), Australian National University Canberra
[12] McKay, B.D.; Miller, M.; Širáň, J., A note on large graphs of diameter two and given maximum degree, J. combin. theory ser. B, 74, 1, 110-118, (1998) · Zbl 0911.05031
[13] Mielants, W., Automorphism groups of elliptic semi-planes, Verh. konink. acad. wetensch. lett. schone kunst. belgië kl. wetensch., 37, 135, 1-94, (1975)
[14] Oehler, M., Endliche biaffine inzidenzebenen, Geom. dedicata, 4, 2/3/4, 419-436, (1975) · Zbl 0321.50009
[15] Pickert, G., Biaffine inzidenzebenen, orthogonale lateinische quadrate und 2-assoziationsschemata, Geom. dedicata, 7, 3, 281-285, (1978) · Zbl 0379.50010
[16] Šiagiová, J., A note on the mckay – miller-širáň graphs, J. combin. theory ser. B, 81, 2, 205-208, (2001) · Zbl 1024.05039
[17] Wild, P., Divisible semibiplanes and conics of Desarguesian biaffine planes, Simon stevin, 58, 1-2, 153-166, (1984) · Zbl 0549.51007
[18] Wild, P., Biaffine planes and divisible semiplanes, J. geom., 25, 2, 121-130, (1985) · Zbl 0576.51011
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.