Inverse Problems in Graph Theory: Nets
- PDF / 436,869 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 5 Downloads / 214 Views
Inverse Problems in Graph Theory: Nets A. A. Makhnev1 · M. P. Golubyatnikov2 · Wenbin Guo3 Received: 27 July 2018 / Revised: 19 September 2018 / Accepted: 28 September 2018 / Published online: 8 December 2018 © School of Mathematical Sciences, University of Science and Technology of China and Springer-Verlag GmbH Germany, part of Springer Nature 2018
Abstract Let Γ be a distance-regular graph of diameter 3 with strong regular graph Γ3 . The determination of the parameters Γ3 over the intersection array of the graph Γ is a direct problem. Finding an intersection array of the graph Γ with respect to the parameters Γ3 is an inverse problem. Previously, inverse problems were solved for Γ3 by Makhnev and Nirova. In this paper, we study the intersection arrays of distance-regular graph Γ of diameter 3, for which the graph Γ¯3 is a pseudo-geometric graph of the net P G m (n, m). New infinite series of admissible intersection arrays for these graphs are found. We also investigate the automorphisms of distance-regular graph with the intersection array {20, 16, 5; 1, 1, 16}. Keywords Distance-regular graph · Pseudo-geometric graph · Strong regular graph Mathematics Subject Classification 05C25 · 05E30
This work is supported by RSF, project 14-11-00061-, Research of the third author was supported by the NNSF of China (11771409).
B
A. A. Makhnev [email protected] M. P. Golubyatnikov [email protected] Wenbin Guo [email protected]
1
Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, Russia
2
Ural Federal University named after the First President of Russia B. N. Yeltsin, Yekaterinburg, Russia
3
University of Science and Technology of China, Hefei, China
123
70
A. A. Makhnev et al.
Introduction We consider undirected graphs without loops and multiple edges. Given vertices a, b in a graph Γ , we denote by d(a, b) the distance between a and b, and by Γi (a) the subgraph induced by Γ , on the set of all vertices, that are at the distance i from a. The subgraph Γ (a) = Γ1 (a) is called the neighborhood of the vertex a. If graph Γ is fixed, then instead of Γ (a) we write [a]. For vertex a we assume a ⊥ = {a} ∪ [a]. If the vertices u, w are at a distance i in Γ , then by bi (u, w) (ci (u, w)) we denote the number of vertices in the intersection Γi+1 (u) (Γi−1 (u)) with [w]. A graph of diameter d is called distance-regular with an intersection array {b0 , . . . , bd−1 ; c1 , . . . , cd }, if the values bi (u, w) and ci (u, w) do not depend on the choice of the vertices u, w on distance i (see [2]). We set ai = ki − bi − ci and ki = |Γi (u)|. (The value of ki does not depend on the choice of the vertex u.) Taylor graph is a distance-regular graph with an intersection array {k, μ, 1; 1, μ, k}. An incidence structure, consisting of points and lines, is called α-partial geometry of order (s, t), if there are integers s, t, α such that each line is incident with s + 1 points, each point is incident with t + 1 lines (lines intersect no more than one point), and for any point a,
Data Loading...
