Geodesic
The vertex connectivity of some classes of divisible design graphs
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 426-438.

Voir la notice de l'article provenant de la source Math-Net.Ru

A $k$-regular graph is called a divisible design graph if its vertex set can be partitioned into $m$ classes of size $n$, such that two distinct vertices from the same class have exactly $\lambda_1$ common neighbours, and two vertices from different classes have exactly $\lambda_2$ common neighbours. In this paper, we find the vertex connectivity of some classes of divisible design graphs, in particular, we present examples of divisible design graphs, whose vertex connectivity is less than $k$, where $k$ is the degree of a vertex. We also show that the vertex connectivity of one series of divisible design graphs may differ from k by any power of $2$.
Keywords: Deza graph, divisible design graph, strongly regular graph, vertex connectivity. 
@article{SEMR_2022_19_2_a26,
     author = {D. I. Panasenko},
     title = {The vertex connectivity of some classes of divisible design graphs},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {426--438},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a26/}
}
TY  - JOUR
AU  - D. I. Panasenko
TI  - The vertex connectivity of some classes of divisible design graphs
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2022
SP  - 426
EP  - 438
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a26/
LA  - en
ID  - SEMR_2022_19_2_a26
ER  - 
%0 Journal Article
%A D. I. Panasenko
%T The vertex connectivity of some classes of divisible design graphs
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2022
%P 426-438
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a26/
%G en
%F SEMR_2022_19_2_a26
D. I. Panasenko. The vertex connectivity of some classes of divisible design graphs. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 426-438. http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a26/

[1] A.E. Brouwer, A. Cohen, A. Neumaier, Distance-regular graphs, Springer, Berlin etc, 1989 | MR | Zbl

[2] A.E. Brouwer, W.H. Haemers, Spectra of graphs, Springer, Berlin, 2012 | MR | Zbl

[3] A.E. Brouwer, J.H. Koolen, “The vertex-connectivity of a distance-regular graph”, Eur. J. Comb., 30:3 (2009), 668–673 | DOI | MR | Zbl

[4] A.E. Brouwer, D.M. Mesner, “The connectivity of strongly regular graphs”, Eur. J. Comb., 6 (1985), 215–216 | DOI | MR | Zbl

[5] C. Godsil, G. Royle, Algebraic graph theory, Springer-Verlag, New York, 2001 | MR | Zbl

[6] D. Crnković, W.H. Haemers, “Walk-regular divisible design graphs”, Des. Codes Cryptography, 72:1 (2014), 165–175 | DOI | MR | Zbl

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

[8] A.L. Gavrilyuk, S. Goryainov, V.V. Kabanov, “On the vertex connectivity of Deza graphs”, Proc. Steklov Inst. Math., 285, Suppl. 1 (2014), S68–S77 | DOI | MR | Zbl

[9] S. Goryainov, W.H. Haemers, V.V. Kabanov, L. Shalaginov, “Deza graphs with parameters $(n,k,k-1,a)$ and $\beta = 1$”, J. Comb. Des., 17:3 (2019), 188–202 | DOI | MR | Zbl

[10] 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 | DOI | MR | Zbl

[11] W.H Haemers, H. Kharaghani, M.A. Meulenberg, “Divisible design graphs”, J. Comb. Theory, Ser. A, 118:3 (2011), 978–992 | DOI | MR | Zbl

[12] F. Harary, Graph theory, Addison-Wesley, Mass. etc, 1969 | MR | Zbl

[13] V.V. Kabanov, A.A. Makhnev, D.V. Paduchikh, “On strongly regular graphs with eigenvalue $2$ and their extensions”, Dokl. Math., 81:2 (2010), 268–271 | DOI | MR | Zbl

[14] M.A. Meulenberg, Divisible design graphs, Master's thesis, Tilburg University, 2008

[15] D. Panasenko, L. Shalaginov, “Classification of divisible design graphs with at most $39$ vertices”, J. Comb. Des., 30:4 (2022), 205–219 | DOI | MR

[16] J.-M. Xu, C. Yang, “Connectivity of lexicographic product and direct product of graphs”, Ars Comb., 111 (2013), 3–12 | MR | Zbl