The Largest Moore Graph and a Distance-Regular Graph with Intersection Array {55, 54, 2; 1, 1, 54}
- PDF / 187,494 Bytes
- 6 Pages / 594 x 792 pts Page_size
- 78 Downloads / 155 Views
Algebra and Logic, Vol. 59, No. 4, September, 2020 (Russian Original Vol. 59, No. 4, July-August, 2020)
THE LARGEST MOORE GRAPH AND A DISTANCE-REGULAR GRAPH WITH INTERSECTION ARRAY {55, 54, 2; 1, 1, 54} A. A. Makhnev and D. V. Paduchikh
UDC 519.17+512.54
Keywords: Moore graph, distance-regular graph, automorphism. We point out possible automorphisms of a distance-regular graph Γ with intersection array {55, 54, 2; 1, 1, 54} and spectrum 551 , 71617 , −1110 , −81408 . We deal with undirected graphs without loops and multiple edges. If a and b are vertices of a graph Γ, then by d(a, b) we denote the distance between a and b, and by Γi (a) a subgraph of Γ induced by a set of vertices that are at a distance i from a vertex a in Γ. The subgraph Γ1 (a) is called the neighborhood of a vertex a and is denoted [a] if Γ is fixed. If u and w are i apart in Γ, then by bi (u, w) (by ci (u, w)) we denote the number of vertices in the intersection of Γi+1 (u) (of Γi−1 (u)) with [w]. A graph of diameter d is said to be distance-regular with intersection array {b0 , . . . , bd−1 ; c1 , . . . , cd } if the values bi (u, w) and ci (u, w) do not depend on the choice of vertices u and w at a distance i (see [1]). Put ai = k − bi − ci and ki = |Γi (u)| (the value ki does not depend on the choice of a vertex u). A Taylor graph is a distance-regular graph with intersection array {k, μ, 1; 1, μ, k}. An incidence structure consisting of points and straight lines is called an α-partial geometry of order (s, t) if every straight line contains s + 1 points, every point lies on t + 1 straight lines (the lines intersect in at most one point), and for any point a not on a straight line L, there are exactly α lines passing through a and intersecting L (written pGα (s, t)). If α = 1, then the geometry is called a generalized quadrangle. The point graph of a geometry of points and straight lines is a graph whose vertices are the points of the geometry and two distinct vertices are adjacent if they lie on a common line. It is 1
Krasovskii Institute of Mathematics and Mechanics, Ural Branch, Russian Academy of Sciences, Yekaterinburg, Russia; [email protected]. 2 Krasovskii Institute of Mathematics and Mechanics, Ural Branch, Russian Academy of Sciences, Yekaterinburg, Russia; [email protected]. Translated from Algebra i Logika, Vol. 59, No. 4, pp. 471-479, July-August, 2020. Russian DOI: 10.33048/alglog.2020.59.404. Original article submitted February 14, 2019; accepted November 24, 2020. 322
c 2020 Springer Science+Business Media, LLC 0002-5232/20/5904-0322
easy to see that the point graph of a partial geometry pGα (s, t) is strongly regular with parameters v = (s + 1)(1 + st/α), k = s(t + 1), λ = (s − 1) + (α − 1)t, and μ = α(t + 1). A strongly regular graph with these parameters is called a pseudogeometric graph for pGα (s, t). In such graphs, the Hoffman boundary for cliques equals s + 1 and every vertex outside an (s + 1)-clique L is adjacent to α vertices in L. If a regular graph of degree k and diameter d has v vertices, then v ≤ 1
Data Loading...
