Geodesic
On Deza graphs with parameters of lattice graphs
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 16 (2010) no. 3, pp. 117-120
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

A Deza graph with parameters $(v,k,b,a)$, where $b\ge a$, is a $k$-regular graph on $v$ vertices in which any two vertices have either $a$ or $b$ common neighbors. A strongly regular graph with parameters $(v,k,\lambda,\mu)$ is a $k$-regular graph on $v$ vertices in which any two adjacent vertices have exactly $\lambda$ common neighbors and any two nonadjacent vertices have $\mu$ common neighbors. An strictly Deza graph is a Deza graph of diameter 2 that is not strongly regular. If a strongly regular graph has an involutive automorphism that transposes nonadjacent vertices only, then it is known that this automorphism can be used to obtain a Deza graph with the parameters of the initial strongly regular graph. We find all the automorphisms of strongly regular lattice $n\times n$ graphs with $n\ge3$ that satisfy the above condition. It turns out that there is exactly one such automorphism for odd $n$ and exactly two automorphisms for even $n$. Neighborhoods of exact Deza graphs obtained by means of this automorphism are found and a characterization of such strictly Deza graph with respect to its parameters and the structure of neighborhoods is obtained.
Keywords: line graph, strongly regular graph, Deza graph, strictly Deza graph, involutive automorphism. 
@article{TIMM_2010_16_3_a10,
     author = {V. V. Kabanov and L. V. Shalaginov},
     title = {On {Deza} graphs with parameters of lattice graphs},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {117--120},
     year = {2010},
     volume = {16},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a10/}
}
TY  - JOUR
AU  - V. V. Kabanov
AU  - L. V. Shalaginov
TI  - On Deza graphs with parameters of lattice graphs
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2010
SP  - 117
EP  - 120
VL  - 16
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a10/
LA  - ru
ID  - TIMM_2010_16_3_a10
ER  - 
%0 Journal Article
%A V. V. Kabanov
%A L. V. Shalaginov
%T On Deza graphs with parameters of lattice graphs
%J Trudy Instituta matematiki i mehaniki
%D 2010
%P 117-120
%V 16
%N 3
%U http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a10/
%G ru
%F TIMM_2010_16_3_a10
V. V. Kabanov; L. V. Shalaginov. On Deza graphs with parameters of lattice graphs. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 16 (2010) no. 3, pp. 117-120. http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a10/

[1] Bose R. C., “Strongly regular graphs, partial geometries and partially balanced designs”, Pacific J. Math., 13 (1963), 389–419 | MR | Zbl

[2] Brouwer A. E., Cohen A. M., Neumaier A., Distance regular graphs, Springer-Verlag, Berlin etc., 1989, 495 pp. | MR | Zbl

[3] Erickson M., Fernando S., Haemers W. H., Hardy D., Hemmeter J., “Deza graphs: a generalization of strongly regular graphs”, J. Comb. Designs, 7 (1999), 359–405 | 3.0.CO;2-U class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR

[4] Shrikhande S. S., “The uniqueness of the $L_2$ association scheme”, Ann. Math. Statist., 30 (1959), 781–798 | DOI | MR | Zbl