GRAPHS \(\Gamma\) OF DIAMETER 4 FOR WHICH \(\Gamma_{3,4}\) IS A STRONGLY REGULAR GRAPH WITH \(\mu=4,6\)

Alexander A. Makhnev     (Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, 16 S. Kovalevskaya Str., Ekaterinburg, 620108, Russian Federation; University Hainan Province, 58 Renmin Av., Haikou 570228, Hainan, P.R. China, Russian Federation)
Mikhail P. Golubyatnikov     (Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, 16 S. Kovalevskaya Str., Ekaterinburg, 620108; Ural Federal University, 19 Mira Str., Ekaterinburg, 620002, Russian Federation)
Konstantin S. Efimov     (Ural State Mining University, 30 Kuibyshev Str., Ekaterinburg, 620144, Russian Federation; Ural Federal University, 19 Mira Str., Ekaterinburg, 620002, Russian Federation)

Abstract


We consider antipodal graphs \(\Gamma\) of diameter 4 for which  \(\Gamma_{1,2}\) is a strongly regular graph. A.A. Makhnev and D.V. Paduchikh noticed that, in this case, \(\Delta=\Gamma_{3,4}\) is a strongly regular graph without triangles. It is known that in the cases \(\mu=\mu(\Delta)\in \{2,4,6\}\) there are infinite series of admissible parameters of strongly regular graphs with \(k(\Delta)=\mu(r+1)+r^2\), where \(r\) and \(s=-(\mu+r)\) are nonprincipal eigenvalues of \(\Delta\). This paper studies graphs with \(\mu(\Delta)=4\) and 6. In these cases, \(\Gamma\) has intersection arrays \(\{{r^2+4r+3},{r^2+4r},4,1;1,4,r^2+4r,r^2+4r+3\}\) and \(\{r^2+6r+5,r^2+6r,6,1;1,6,r^2+6r,r^2+6r+5\}\), respectively. It is proved that graphs with such intersection arrays do not exist.


Keywords


Distance-regular graph, Strongly regular graph, Triple intersection numbers

Full Text:

PDF

References


  1. Brouwer A.E., Cohen A.M., Neumaier A. Distance–Regular Graphs. Berlin, Heidelberg: Springer–Verlag, 1989. 495 p. DOI: 10.1007/978-3-642-74341-2
  2. Coolsaet K., Jurišić A. Using equality in the Krein conditions to prove nonexistence of sertain distance-regular graphs. J. Combin. Theory Ser. A, 2018. Vol. 115, No. 6. P. 1086–1095. DOI: 10.1016/j.jcta.2007.12.001
  3. Makhnev A.A., Paduchikh D.V. Inverse problems in the class of distance-regular graphs of diameter 4. Proc. Steklov Inst. Math., 2022. Vol. 317, No. Suppl. 1. P. S121–S129. DOI: 10.1134/S0081543822030105




DOI: http://dx.doi.org/10.15826/umj.2024.1.007

Article Metrics

Metrics Loading ...

Refbacks

  • There are currently no refbacks.