On Deza graphs with parameters of triangular graphs

L. V. Shalaginov

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 17 (2011) no. 1, pp. 294-298

Résumé

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 exactly $\mu$ common neighbors. A 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 automorphisms of triangular graphs that satisfy the above condition. It turns out that there is exactly one such automorphism up to the numbering of vertices. Neighborhoods of a strictly Deza graph 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.

Détail

Keywords: line graph, strongly regular graph, triangular graph, Deza graph, exact Deza graph, involutive automorphism.