|
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.
Received March 6, 2022, published August 17, 2022
Citation:
D. I. Panasenko, “The vertex connectivity of some classes of divisible design graphs”, Sib. Èlektron. Mat. Izv., 19:2 (2022), 426–438
Linking options:
https://www.mathnet.ru/eng/semr1513 https://www.mathnet.ru/eng/semr/v19/i2/p426
|
Statistics & downloads: |
Abstract page: | 71 | Full-text PDF : | 18 | References: | 21 |
|