RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2021, том 18, выпуск 2, страницы 1742–1756 (Mi semr1475)

Эта публикация цитируется в 1 статье

Дискретная математика и математическая кибернетика

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

Аннотация: 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.

Ключевые слова: divisible desing graph, divisible design, Deza graph, lattice graph.

УДК: 519.17

MSC: 05C50, 05E10, 15A18

Поступила 13 августа 2021 г., опубликована 30 декабря 2021 г.

Язык публикации: английский

DOI: 10.33048/semi.2021.18.134



Реферативные базы данных:


© МИАН, 2024