This article is cited in
1 paper
Discrete mathematics and mathematical cybernetics
Divisible design graphs with parameters $(4n,n+2,n-2,2,4,n)$ and $(4n,3n-2,3n-6,2n-2,4,n)$
L. Shalaginov Chelyabinsk State University, 129, Bratiev Kashirinykh st., Chelyabinsk, 454001, Russia
Abstract:
A
$k$-regular graph is called a divisible design graph (DDG for short) 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 neighbors, and two vertices from different classes have exactly
$\lambda_2$ common neighbors. A
$4$-by-
$n$-lattice graph is the line graph of
$K_{4,n}$. This graph is a DDG with parameters
$(4n,n+2,n-2,2,4,n)$. In the paper, we consider DDGs with these parameters. We prove that if
$n$ is odd, then such graph can only be a
$4$-by-
$n$-lattice graph. If
$n$ is even, we characterise all DDGs with such parameters. Moreover, we characterise all DDGs with parameters
$(4n,3n-2,3n-6,2n-2,4,n)$ that are related to
$4$-by-
$n$-lattice graphs. Also, we prove that if Deza graph with parameters
$(4n,n+2,n-2,2)$ or
$(4n,3n-2, 3n-6, 2n-2)$ is not a DDG, then
$n\leq 8$. All such Deza graphs were classified by computer search.
Keywords:
divisible desing graph, divisible design, Deza graph, lattice graph.
UDC:
519.17
MSC: 05C50,
05E10,
15A18 Received August 13, 2021, published
December 30, 2021
Language: English
DOI:
10.33048/semi.2021.18.134