RUS  ENG
Full version
JOURNALS // Trudy Instituta Matematiki i Mekhaniki UrO RAN // Archive

Trudy Inst. Mat. i Mekh. UrO RAN, 2016 Volume 22, Number 3, Pages 50–61 (Mi timm1321)

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


 English version:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2017, 297, suppl. 1, 97–107

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024