|
This article is cited in 2 scientific papers (total 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.
Received: 10.12.2015
Citation:
S. V. Goryainov, G. S. Isakova, V. V. Kabanov, N. V. Maslova, L. V. Shalaginov, “On Deza graphs with disconnected second neighborhood of a vertex”, Trudy Inst. Mat. i Mekh. UrO RAN, 22, no. 3, 2016, 50–61; Proc. Steklov Inst. Math. (Suppl.), 297, suppl. 1 (2017), 97–107
Linking options:
https://www.mathnet.ru/eng/timm1321 https://www.mathnet.ru/eng/timm/v22/i3/p50
|
Statistics & downloads: |
Abstract page: | 423 | Full-text PDF : | 81 | References: | 41 | First page: | 9 |
|