On Deza graphs with disconnected second neighborhood of a vertex

S. V. Goryainov ; G. S. Isakova ; V. V. Kabanov ; N. V. Maslova ; L. V. Shalaginov

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 22 (2016) no. 3, pp. 50-61

Résumé

A graph $\Gamma$ is called a Deza graph if it is regular and the number of common neighbors of two distinct vertices is one of two values. A Deza graph $\Gamma$ is called a strictly Deza graph if it has diameter $2$ and is not strongly regular. In 1992, Gardiner, Godsil, Hensel, and Royle proved that a strongly regular graph that contains a vertex with disconnected second neighborhood is a complete multipartite graph with parts of the same size and this size is greater than or equal to $2$. In this paper we study strictly Deza graphs with disconnected second neighborhoods of vertices. In Section 2, we prove that, if each vertex of a strictly Deza graph has disconnected second neighborhood, then the graph is either edge-regular or coedge-regular. In Sections 3 and 4, we consider strictly Deza graphs that contain at least one vertex with disconnected second neighborhood. In Section 3, we show that, if such a graph is edge-regular, then it is an $s$-coclique extension of a strongly regular graph with parameters $(n,k,\lambda,\mu)$, where $s$ is integer, $s \ge 2$, and $\lambda=\mu$. In Section 4, we show that, if such a graph is coedge-regular, then it is a $2$-clique extension of a complete multipartite graph with parts of the same size greater than or equal to $3$.

Détail

Keywords: Deza graph, strictly Deza graph, disconnected second neighborhood, edge-regular graph, coedge-regular graph.