RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2022 Volume 19, Issue 2, Pages 426–438 (Mi semr1513)

Discrete mathematics and mathematical cybernetics

The vertex connectivity of some classes of divisible design graphs

D. I. Panasenkoab

a Chelyabinsk State University, 129, Bratiev Kashirinykh str., Chelyabinsk, 454001, Russia
b N.N. Krasovskii Institute of Mathematics and Mechanics, 16, S. Kovalevskaya str., Yekaterinburg, 620108, Russia

Abstract: 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.

UDC: 519.17

MSC: 05C50, 05E10, 15A18

Received March 6, 2022, published August 17, 2022

Language: English

DOI: 10.33048/semi.2022.19.038



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024