This article is cited in
2 papers
On Deza graphs with disconnected second neighborhood of a vertex
S. V. Goryainovab,
G. S. Isakovaa,
V. V. Kabanovb,
N. V. Maslovabc,
L. V. Shalaginova a Chelyabinsk State University
b Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg
c Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg
Abstract:
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$.
Keywords:
Deza graph, strictly Deza graph, disconnected second neighborhood, edge-regular graph, coedge-regular graph.
UDC:
519.17
MSC: 05C40,
05C07 Received: 10.12.2015
DOI:
10.21538/0134-4889-2016-22-3-50-61