I.N. Belousov, A.A. Makhnev. Inverse problems in the theory of distance-regular graphs: Dual 2-designs ... P. 44-51

Let $\Gamma$ be a distance-regular graph of diameter 3 with a strongly regular graph $\Gamma_3$. Finding the parameters of $\Gamma_3$ from the intersection array of $\Gamma$ is a direct problem, and finding the intersection array of $\Gamma$ from the parameters of $\Gamma_3$ is its inverse. The direct and inverse problems were solved by A.A. Makhnev and M.S. Nirova: if a graph $\Gamma$ with intersection array $\{k,b_1,b_2;1,c_2,c_3\}$ has eigenvalue $\theta_2=-1$, then the graph complementary to $\Gamma_3$ is pseudo-geometric for $pG_{c_3}(k,b_1/c_2)$. Conversely, if $\Gamma_3$ is a pseudo-geometric graph for $pG_{\alpha}(k,t)$, then $\Gamma$ has intersection array $\{k,c_2t,k-\alpha+1;1,c_2,\alpha\}$, where $k-\alpha+1\le c_2t<k$ and $1\le c_2\le \alpha.$ Distance-regular graphs $\Gamma$ of diameter 3 for which the graph $\Gamma_3$ ($\bar \Gamma_3$) is pseudo\-geometric for a net or a generalized quadrangle were studied earlier. In this paper we study intersection arrays of distance-regular graphs $\Gamma$ of diameter 3 for which the graph $\Gamma_3$ ($\bar \Gamma_3$) is pseudo-geometric for a dual 2-design $pG_{t+1}(l,t)$. New infinite families of feasible intersection arrays are found: $$\{m(m^2-1),m^2(m-1),m^2;1,1,(m^2-1)(m-1)\} , \{m(m+1),(m+2)(m-1),m+2;1,1,m^2-1\},$$ and $$\{2m(m-1),(2m-1)(m-1),2m-1;1,1,2(m-1)^2\},$$ where $m\equiv\pm 1$ (mod 3). The known families of Steiner 2-designs are unitals, designs corresponding to odd-order projective planes containing a hyperoval, designs of points and lines of projective spaces $PG(n,q)$, and designs of points and lines of affine spaces $AG(n,q)$. We find feasible intersection arrays of a distance-regular graph $\Gamma$ of diameter 3 for which the graph $\Gamma_3$ ($\bar \Gamma_3$) is pseudo-geometric for one of the known Steiner 2-designs.

Keywords: distance-regular graph, dual 2-design

Received August 1, 2019

Revised November 8, 2019

Accepted November 25, 2019

Ivan Nikolaevich Belousov, Cand. Sci. (Phys.-Math.), Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia,; Ural Federal University, Yekaterinburg, 620083 Russia, e-mail: i_belousov@mail.ru

Aleksandr Alekseevich Makhnev, Dr. Phys.-Math. Sci., RAS Corresponding Member, Prof., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Ural Federal University, Yekaterinburg, 620083 Russia, e-mail: makhnev@imm.uran.ru

REFERENCES

1.   Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs. Berlin; Heidelberg; N Y: Springer-Verlag, 1989, 495 p. ISBN: 3-540-50619-5 .

2.   Koolen J.H., Park J. Shilla distance-regular graphs. Europ. J. Comb., 2010, vol. 31, pp. 2064–2073.

3.   Jurisic A., Koolen J. Krein parameters and antipodal tight graphs with diameter 3 and 4. Discrete Math., 2002, vol. 244, pp. 181–202. doi: 10.1016/S0012-365X(01)00082-6 

4.   Bang S., Koolen J. Distance-regular graphs of diameter 3 having eigenvakue -1. Linear Algebra Appl., 2017, vol. 531, pp. 38–53. doi: 10.1016/j.laa.2017.05.038 

5.   Makhnev A.A., Nirova M.S. Distance-regular Shilla graphs with $b_2 = c_2$. Math. Notes, 2018, vol. 103, no. 5, pp. 780–792. doi: 10.1134/S0001434618050103 

6.   Barwick S., Ebert G. Unitals in projective planes. N Y etc.: Springer, 2008, 193 p. doi: 10.1007/978-0-387-76366-8 

7.   Assmus E.F., Key J.D. Jr. Designs and their codes. Chap. 8: Steiner systems. Cambridge: Cambridge Univ. Press, 1994, pp. 295–316. doi: 10.1017/CBO9781316529836.009 

8.   Makhnev A.A., Belousov I.N., Paduchikh D.V. Konechnye geometrii i ikh avtomorfizmy [Finite geometries and their automorphisms]. Novosibirsk: SB RAS Publ., 2016, 188. ISBN: 978-5-7692-1521-6 .

9.   Bruck, R.H.; Ryser, H.J. The nonexistence of certain finite projective planes. Canadian J. Math., 1949, vol. 1, pp. 88–93. doi: 10.4153/cjm-1949-009-2 

Cite this article as: I.N.Belousov, A.A.Makhnev. Inverse problems in the theory of distance-regular graphs: Dual 2-designs, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2019, vol. 25, no. 4, pp. 44–51; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2021, Vol. 313, Suppl. 1, pp. S14–S20.