Geodesic
Codes in Shilla distance-regular graphs
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 2, pp. 34-39
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

Let $\Gamma$ be a distance-regular graph of diameter $3$ containing a maximal 1-code $C$, which is locally regular and perfect with respect to the last neighborhood. Then $\Gamma$ has intersection array $\{a(p+1),cp,a+1;1,c,ap\}$ or $\{a(p+1),(a+1)p,c;1,c,ap\}$, where $a=a_3$, $c=c_2$, and $p=p^3_{33}$ (Juri$\check{\mathrm{s}}$i$\acute{\mathrm{c}}$, Vidali). In the first case, $\Gamma$ has eigenvalue $\theta_2=-1$ and the graph $\Gamma_3$ is pseudogeometric for $GQ(p+1,a)$. In the second case, $\Gamma$ is a Shilla graph. We study Shilla graphs in which every two vertices at distance 2 belong to a maximal $1$-code. It is proved that, in the case $\theta_2=-1$, a graph with the specified property is either the Hamming graph $H(3,3)$ or a Johnson graph. We find necessary conditions for the existence of $Q$-polynomial Shilla graphs in which any two vertices at distance 3 lie in a maximal 1-code. In particular, we find two infinite families of feasible intersection arrays of $Q$-polynomial graphs with the specified property: $\{b(b^2-3b)/2,(b-2)(b-1)^2/2,(b-2)t/2;1,bt/2,(b^2-3b)(b-1)/2\}$ (graphs with $p^3_{33}=0$) and $\{b^2(b-4)/2,(b^2-4b+2)(b-1)/2,(b-2)l/2;1,bl/2,(b^2-4b)(b-1)/2\}$ (graphs with $p^3_{33}=1$).
Keywords: distance-regular graph
Mots-clés : graph automorphism. 
@article{TIMM_2018_24_2_a3,
     author = {I. N. Belousov},
     title = {Codes in {Shilla} distance-regular graphs},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {34--39},
     year = {2018},
     volume = {24},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2018_24_2_a3/}
}
TY  - JOUR
AU  - I. N. Belousov
TI  - Codes in Shilla distance-regular graphs
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2018
SP  - 34
EP  - 39
VL  - 24
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2018_24_2_a3/
LA  - ru
ID  - TIMM_2018_24_2_a3
ER  - 
%0 Journal Article
%A I. N. Belousov
%T Codes in Shilla distance-regular graphs
%J Trudy Instituta matematiki i mehaniki
%D 2018
%P 34-39
%V 24
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2018_24_2_a3/
%G ru
%F TIMM_2018_24_2_a3
I. N. Belousov. Codes in Shilla distance-regular graphs. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 2, pp. 34-39. http://geodesic.mathdoc.fr/item/TIMM_2018_24_2_a3/

[1] Brouwer A. E., Cohen A. M., Neumaier A., Distance-regular graphs, Springer-Verlag, Berlin; Heidelberg; N Y, 1989, 495 pp. | MR | Zbl

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

[3] Vidali J., Kode v razdaljno regularnih grafih: Doctorska dissertacija, Univerza v Ljubljani, Ljubljana, 2013, 155 pp.

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

[5] Makhnev A. A., Nirova M. S., “Distantsionno regulyarnye grafy Shilla s $b_2=c_2$”, Mat. zametki, 103:5 (2018), 730–744 | DOI | MR

[6] Belousov I. N., Makhnev A. A., “K teorii grafov Shilla s $b_2=c_2$”, Sib. elektron. mat. izvestiya, 14 (2017), 1135–1146 | DOI | MR

[7] Koolen J.H., Park J., Yu H., “An inequality involving the second largest and smallest eigenvalue of a distance-regular graph”, Linear Algebra Appl., 434:12 (2011), 2404–2412 | DOI | MR | Zbl