Графы разделяемых дизайнов с параметрами (4n,n + 2,n − 2,2,4,n) и (4n, 3n − 2,3n − 6,2n − 2,4,n)
Ключевые слова:
граф разделяемого дизайна, разделяемый дизайн, граф Деза, решетка.Аннотация
Регулярный граф степени k называется графом разделяемого дизайна с параметрами $(v,k,\lambda_1,\lambda_2,m,n)$
(кратко DDG), если множество его вершин можно разделить на m классов мощности n, так что две различные вершины из одного класса имеют ровно $\lambda_1$ общих соседей, а две вершины из разных классов имеют ровно $\lambda_2$ общих соседей. $4{\temes}n$-решетка это реберный граф полного двудольного графа $K_{4,n}$. Этот граф является DDG с параметрами (4n,n + 2,n − 2,2,4,n). В этой статье мы рассматриваем DDG с такими параметрами. Мы доказываем, что при нечетных n граф с такими параметрами может быть только $4{\times}n$-решеткой. При четном $n$ мы описываем все возможные DDG с такимим параметраим. Кроме того, мы описываем все DDG с параметрами (4n,3n − 2,3n − 6,2n − 2,4,n),
которые связаны с графами $4{\times}n$-решеток.
