On Automorphisms of Distance-Regular Graph with Intersection Array $$\{18,15,9;\,1,1,10\}$$
- PDF / 386,648 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 83 Downloads / 154 Views
On Automorphisms of Distance-Regular Graph with Intersection Array {18, 15, 9; 1, 1, 10} A. A. Makhnev1 · D. V. Paduchikh1
Received: 8 May 2015 / Accepted: 10 October 2015 / Published online: 1 December 2015 © School of Mathematical Sciences, University of Science and Technology of China and Springer-Verlag Berlin Heidelberg 2015
Abstract Recently, Makhnev and Nirova found intersection arrays of distance-regular graphs with λ = 2 and at most 4096 vertices. In the case of primitive graphs of diameter 3 with μ = 1 there corresponding arrays are {18, 15, 9; 1, 1, 10}, {33, 30, 8; 1, 1, 30} or {39, 36, 4; 1, 1, 36}. In this work, possible orders and subgraphs of fixed points of the hypothetical distance-regular graph with intersection array {18, 15, 9; 1, 1, 10} are studied. In particular, graph with intersection array {18, 15, 9; 1, 1, 10} is not vertex symmetric. Keywords
Distance-regular graph · Automorphism · Vertex symmetric graph
Mathematics Subject Classification
05C25 · 20B25
1 Introduction We consider undirected graphs without loops and multiple edges. For the vertex a of the graph we denote by i (a) the i-neighborhood of the vertex a, that is, the subgraph induced by on the set of all vertices at the distance i from a. We put [a] = 1 (a), a ⊥ = {a} ∪ [a]. Let be a graph, a, b are two distinct vertices from , the number of vertices in [a] ∩ [b] is denoted by μ(a, b) (by λ(a, b)) if a and b are on the distance 2 from one another (are adjacent) in . Further, the induced subgraph [a] ∩ [b] is called μsubgraph (λ-subgraph). Let be a graph of diameter d. By i we denote graph on the same vertex set in which vertices a and b are adjacent iff d(a, b) = i in .
B 1
A. A. Makhnev [email protected] Institute of Mathematics and Mechanics UB RAS, Yekaterinburg, Russian Federation
123
528
A. A. Makhnev, D. V. Paduchikh
We call by the degree of the vertex the number of vertices in its neighborhood. Graph is called regular of degree k if the degree of any vertex from is equal to k. Graph is called edge regular with parameters (v, k, λ) if it has v vertices, is regular of degree k, and each its edge lies exactly in λ triangles. Graph is an amply regular graph with parameters (v, k, λ, μ) if it is edge regular with corresponding parameters, and [a] ∩ [b] has μ vertices for any two vertices a and b on the distance 2 from one another in . Amply regular graph of diameter 2 is called strongly regular graph. If vertices u and w are on the distance i in graph then by bi (u, w) (by ci (u, w)) we will denote the number of vertices in the intersection of i+1 (u) (correspondingly i−1 (u)) with [w]. Graph of diameter d is called distance regular with intersection array {b0 , b1 , . . . , bd−1 ; c1 , . . . , cd } if values bi (u, w) and ci (u, w) do not depend on choice of vertices u and w on the distance i in for any i = 0, . . . , d. We put ai = k − bi − ci . Notice that for the distance-regular graph the number b0 is a degree, and c1 = 1. Graph of diameter d is called distance transitive if f
Data Loading...
