Geodesic
On Deza graphs with disconnected second neighborhood of a vertex
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 22 (2016) no. 3, pp. 50-61 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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. 
@article{TIMM_2016_22_3_a5,
     author = {S. V. Goryainov and G. S. Isakova and V. V. Kabanov and N. V. Maslova and L. V. Shalaginov},
     title = {On {Deza} graphs with disconnected second neighborhood of a vertex},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {50--61},
     year = {2016},
     volume = {22},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2016_22_3_a5/}
}
TY  - JOUR
AU  - S. V. Goryainov
AU  - G. S. Isakova
AU  - V. V. Kabanov
AU  - N. V. Maslova
AU  - L. V. Shalaginov
TI  - On Deza graphs with disconnected second neighborhood of a vertex
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2016
SP  - 50
EP  - 61
VL  - 22
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TIMM_2016_22_3_a5/
LA  - ru
ID  - TIMM_2016_22_3_a5
ER  - 
%0 Journal Article
%A S. V. Goryainov
%A G. S. Isakova
%A V. V. Kabanov
%A N. V. Maslova
%A L. V. Shalaginov
%T On Deza graphs with disconnected second neighborhood of a vertex
%J Trudy Instituta matematiki i mehaniki
%D 2016
%P 50-61
%V 22
%N 3
%U http://geodesic.mathdoc.fr/item/TIMM_2016_22_3_a5/
%G ru
%F TIMM_2016_22_3_a5
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 Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 22 (2016) no. 3, pp. 50-61. http://geodesic.mathdoc.fr/item/TIMM_2016_22_3_a5/

[1] A.V. Mityanina, “O $K_{1,3}$-svobodnykh tochnykh grafakh Deza”, Tr. In-ta matematiki i mekhaniki UrO RAN, 22:1, 231–234 | MR

[2] Biggs N., Algebraic graph theory, Cambridge University Press, Cambridge, 1993, 216 pp. | MR

[3] Brouwer A.E., Cohen A.M., Neumaier A., Distance-regular graphs, Springer-Verlag, Berlin, 1989, 495 pp. | MR | Zbl

[4] Brouwer A.E., van Lint J. H., “Strongly regular graphs and partial geometries, enumeration and design”, Proc. of the Silver Jubilee Conference at the University of Waterloo, eds. D.M. Jackson and S.A. Vanstone, Academic Press, Toronto, 1984, 85–122 | MR

[5] Cioaba S.M., Koolen J.H., “On the connectedness of the complement of a ball in distance-regular graphs”, J. Algebraic Combinator., 38:1 (2013), 191–195 | DOI | MR | Zbl

[6] M. Erickson, S. Fernando, W.H. Haemers, D. Hardy, J. Hemmeter, “Deza graphs: a generalization of strongly regular graphs”, J. Comb. Designs, 7 (1999), 359–405 | 3.0.CO;2-U class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR

[7] Diestel R., Graph theory, Springer-Verlag, Berlin, 2010, 410 pp. | MR

[8] A.D. Gardiner, C.D. Godsil., A.D. Hensel, G.F. Royle, “Second neighbourhoods of strongly regular graphs”, Discrete Math., 103 (1992), 161–170 | DOI | MR | Zbl