Geodesic
Inverse problems in distance-regular graphs theory
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 3, pp. 133-144
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

For a distance-regular graph $\Gamma$ of diameter 3, the graph $\Gamma_i$ can be strongly regular for $i=2$ or $3$. Finding the parameters of $\Gamma_i$ given the intersection array of $\Gamma$ is a direct problem, and finding the intersection array of $\Gamma$ given the parameters of $\Gamma_i$ is the inverse problem. The direct and inverse problems were solved earlier by A.A. Makhnev and M.S. Nirova for $i=3$. In the present paper, we solve the inverse problem for $i=2$: given the parameters of a strongly regular graph $\Gamma_2$, we find the intersection array of a distance-regular graph $\Gamma$ of diameter 3. It is proved that $\Gamma_2$ is not a graph in the half case. We also refine Nirova's results on distance-regular graphs $\Gamma$ of diameter 3 for which $\Gamma_2$ and $\Gamma_3$ are strongly regular. New infinite series of admissible intersection arrays are found: $\{r^2+3r+1,r(r+1),r+2;1,r+1,r(r+2)\}$ for odd $r$ divisible by 3 and $\{2r^2+5r+2,r(2r+2),2r+3;1,2r+2,r(2r+3)\}$ for $r$ indivisible by $3$ and not congruent to $\pm 1$ modulo $5$.
Keywords: strongly regular graph, distance-regular graph, intersection array. 
@article{TIMM_2018_24_3_a12,
     author = {A. A. Makhnev and D. V. Paduchikh},
     title = {Inverse problems in distance-regular graphs theory},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {133--144},
     year = {2018},
     volume = {24},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2018_24_3_a12/}
}
TY  - JOUR
AU  - A. A. Makhnev
AU  - D. V. Paduchikh
TI  - Inverse problems in distance-regular graphs theory
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2018
SP  - 133
EP  - 144
VL  - 24
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TIMM_2018_24_3_a12/
LA  - ru
ID  - TIMM_2018_24_3_a12
ER  - 
%0 Journal Article
%A A. A. Makhnev
%A D. V. Paduchikh
%T Inverse problems in distance-regular graphs theory
%J Trudy Instituta matematiki i mehaniki
%D 2018
%P 133-144
%V 24
%N 3
%U http://geodesic.mathdoc.fr/item/TIMM_2018_24_3_a12/
%G ru
%F TIMM_2018_24_3_a12
A. A. Makhnev; D. V. Paduchikh. Inverse problems in distance-regular graphs theory. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 3, pp. 133-144. http://geodesic.mathdoc.fr/item/TIMM_2018_24_3_a12/

[1] Brouwer A.E., Cohen A.M., Neumaier A., Distance-regular graphs, Springer-Verlag, Berlin, 1989, 495 pp.

[2] Makhnev A., Nirova M., “On distance-regular Shilla graphs with $b_2 = c_2$”, Mat. Zametki, 103:5 (2018), 730–744 | DOI

[3] Coolsaet K., Jurisic A., “Using equality in the Krein conditions to prove the nonexistence of certain distance-regular graphs”, J. Comb. Theory Ser. A, 115 (2008), 1086–1095 | DOI

[4] Shi M., Krotov D., Sole P., A new distance-regular graph of diameter 3 on 1024 vertices, [e-resource], 2018, 12 pp., arXiv: https://arxiv.org/pdf/1806.07069.pdf

[5] Gavrilyuk A., Makhnev A., “Distance-regular graph with intersection array {45,30,7;1,2,27} does not exist”, Discrete Math. Appl., 23 (2013), 225–244

[6] Gavrilyuk A., Makhnev A., “Distance-regular graphs with intersection arrays {52,35,16;1,4,28} and {69,48,24;1,4,46} do not exist”, Des. Codes Cryptogr., 65 (2012), 49–54

[7] Urlep M., “Triple intersection numbers in Q-polinomial distance-regular graphs”, Europ. J. Comb., 33 (2012), 1246–1252

[8] Koolen J.H., Park J., “Shilla distance-regular graphs”, Europ. J. Comb., 31:8 (2010), 2064–2073 | DOI

[9] Nirova M., “On distance-regular graphs $\Gamma$ with strongly regular $\Gamma_2$ and $\Gamma_3$”, Sibirean Electr. Math. Reports, 15 (2018), 175–185 | DOI

[10] Jurisic A., Vidali J., “Extremal 1-codes in distance-regular graphs of diameter 3”, Des. Codes Cryptogr., 65:1–2 (2012), 29–47 | DOI

[11] Koolen J.H., Park J., “A relationship between the diameter and the intersection number $c_2$ for a distance-regular graphs”, Des. Codes Cryptogr, 65:1–2 (2012), 55–63 | DOI

[12] Degraer J., Isomorphism-free exhaustive generation algorithms for association schemes, PHD, Univ. Gent, Gent, 2007, 240 pp.