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$.
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
\Bibitem{GorIsaKab16}
\by S.~V.~Goryainov, G.~S.~Isakova, V.~V.~Kabanov, N.~V.~Maslova, L.~V.~Shalaginov
\paper On Deza graphs with disconnected second neighborhood of a vertex
\serial Trudy Inst. Mat. i Mekh. UrO RAN
\yr 2016
\vol 22
\issue 3
\pages 50--61
\mathnet{http://mi.mathnet.ru/timm1321}
\crossref{https://doi.org/10.21538/0134-4889-2016-22-3-50-61}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3555710}
\elib{https://elibrary.ru/item.asp?id=26530877}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2017
\vol 297
\issue , suppl. 1
\pages 97--107
\crossref{https://doi.org/10.1134/S008154381705011X}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000410252500011}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85029211180}
Linking options:
https://www.mathnet.ru/eng/timm1321
https://www.mathnet.ru/eng/timm/v22/i3/p50
This publication is cited in the following 2 articles:
Zhengyu Guo, Gengsheng Zhang, “On the second neighbourhoods of quasi-strongly regular graphs”, Discrete Mathematics, 345:8 (2022), 112922
S. Goryainov, D. Panasenko, “On vertex connectivity of Deza graphs with parameters of the complements to seidel graphs”, Eur. J. Comb., 80 (2019), 143–150