О двудольных Q-полиномиальных графах диаметра, не большего 5
Автор: Биткина В.В., Махнев А.А.
Журнал: Владикавказский математический журнал @vmj-ru
Статья в выпуске: 3 т.27, 2025 года.
Бесплатный доступ
Пусть u - вершина двудольного Q-полиномиального дистанционно регулярного графа Γ диаметра D≥3, Σ=ΓD(u) и Λ=Σ2. Тогда Λ - дистанционно регулярный Q-полиномиальный граф. В случаях D=4 и D=5 граф Λ является сильно регулярным Q-полиномиальным. Половинный граф Γ2 сильно регулярен и Λ - окрестность вершины в дополнении к Γ2. Поэтому необходимое условие Q-полиномиальности Γ - это сильная регулярность окрестностей и антиокрестностей вершин в Λ. Двудольный дистанционно регулярный граф Γ диаметра D∈{4,5} назовем почти Q-полиномиальным, если окрестности и антиокрестности вершин в дополнении его половинного графа сильно регулярны. Имеется два допустимых массива пересечений Q-полиномиальных графов: {10,9,8,7,6;1,2,3,4,10} (свернутый 10-куб) и {55,54,50,35,10;1,5,20,45,55}. Эти графы имеют сильно регулярные графы Λ (параметры (126,25,8,4) и (210,99,48,45)) и окрестности вершин в Λ (параметры (25,8,4,2) и (99,48,22,24)). Имеются два допустимых массива пересечений, отвечающих графам на 704 вершинах: {26,25,24,2,1;1,2,24,25,26} и {36,34,32,4,1;1,4,32,34,36}. В работе изучаются почти \mbox{Q-полиномиальные} графы диаметра 5. Доказано, что дистанционно регулярные графы с массивами пересечений {26,25,24,2,1;1,2,24,25,26} и {36,35,32,4,1;1,4,32,35,36} не существуют.
Дистанционно регулярный граф, Q-полиномиальный граф, двудольный граф
Короткий адрес: https://sciup.org/143184857
IDR: 143184857 | УДК: 519.17 | DOI: 10.46698/y5679-0662-9249-a
On Bipartite Q-Polynomial Graphs of Diameter Not Greater than 5
Let u be a vertex of a bipartite Q-polynomial distance-regular graph of diameter D > 3, = D(u), and = 2. Then is a distance-regular Q-polynomial graph. In the cases D = 4 and D = 5 the graph is strongly regular Q-polynomial. The half graph 2 is strongly regular and is a neighbourhood of a vertex in the complement of 2. Therefore, a necessary condition for Q-polynomiality of is the strong regularity of neighbourhoods and antineighbourhoods of vertices in . A bipartite distance-regular graph of diameter D ∈ {4, 5} is called almost Q-polynomial if neighbourhoods and antineighbourhoods of vertices in its half-graph are strongly regular. There are two admissible intersection arrays of Q-polynomial graphs: {10, 9, 8, 7, 6; 1, 2, 3, 4, 10} (a folded 10-cube) and {55, 54, 50, 35, 10; 1, 5, 20, 45, 55}. These graphs have strongly regular graphs (parameters (126, 25, 8, 4) and (210, 99, 48, 45)) and neighbourhoods of vertices in (parameters (25, 8, 4, 2) and (99, 48, 22, 24)). There are two admissible intersection arrays corresponding to graphs on 704 vertices: {26, 25, 24, 2, 1; 1, 2, 24, 25, 26} and {36, 34, 32, 4, 1; 1, 4, 32, 34, 36}. In this manuscript we study almost Q-polynomial graphs of diameter 5. We obtain that distance-regular graphs with intersection arrays {26, 25, 24, 2, 1; 1, 2, 24, 25, 26} and {36, 35, 32, 4, 1; 1, 4, 32, 35, 36} do not exist.
Текст научной статьи О двудольных Q-полиномиальных графах диаметра, не большего 5
Рассматриваются неориентированные графы без петель и кратных ребер. Если вершины u, w находятся на расстоянии i в графе Г, то через bi(u, w) (через Ci(u, w)) обозначим число вершин в пересечении ri+i(u) (в пересечении ri-i(u)) с [w]. Граф диаметра d называется дистанционно регулярным с массивом пересечений {bo,..., bd-i; ci,... ,Cd}, если значения bi = bi(u,w) и Ci = Ci(u,w) не зависят от выбора вершин u, w на расстоянии i. Положим ai = k — bi — ci и ki = |ri(u)| (значение ki не зависит от выбора вершины u). Числа пересечений графа pj, параметры Крейна qij и Q-полиномиальный граф определены в [1] (стр. 43 и 48 соответственно).
Для двудольного дистанционно регулярного графа Γ половинным графом называется связная компонента в Γ 2 . Для антиподального дистанционно регулярного графа Γ антиподальным частным Γ ′ называется граф, вершинами которого являются антиподальные классы графа Г и две вершины u ' , w ‘ смежны, если некоторые вершины u G u ' , w G w' смежны в Г. Пусть u — вершина двудольного Q-полиномиального дистанционно регулярного графа Г диаметра D > 3, X = r D (u) и Л = S 2 . Тогда Л — дистанционно регулярный Q-полиномиальный граф (Джон Кохман [2]). Имеется два допустимых массива пересечений Q-полиномиальных графов: { 10, 9, 8, 7, 6; 1, 2, 3,4,10 } (свернутый 10-куб) и { 55, 54, 50, 35,10; 1, 5, 20,45, 55 } . Эти графы имеют сильно регулярные графы Л (параметры (126, 25, 8, 4) и (210, 99, 48, 45)) и окрестности вершин в Л (параметры (25, 8,4, 2) и (99, 48, 22, 24)). В [3] доказано, что дистанционно регулярный граф с массивом пересечений { 55, 54, 50, 35,10; 1, 5, 20, 45, 55 } не существует. Имеются два допустимых массива пересечений, отвечающих графам на 704 вершинах: { 26, 25, 24, 2,1; 1, 2, 24, 25, 26 } и { 36, 35, 32,4,1; 1,4, 32, 35, 36 } . Антиподальные частные этих графов сильно регулярны с параметрами (352, 26, 0, 2) и (352, 36, 0, 4) соответственно.
Теорема 1. Дистанционно регулярный граф с массивом пересечений { 26, 25, 24, 2,1; 1, 2, 24, 25, 26 } не существует.
Теорема 2. Дистанционно регулярный граф с массивом пересечений { 36, 35, 32,4,1; 1, 4, 32, 35, 36 } не существует.
Напомним, что сильно регулярный граф без треугольников существует тогда и только тогда, когда существует его двудольное удвоение диаметра 5 (см. из [1, теорема 1.11.1, п. (vi)]). Отсюда имеем следствие.
Следствие. Сильно регулярные графы с параметрами (352, 26, 0, 2) и (352, 36, 0,4) не существуют.
-
1. Тройные числа пересечений
Для доказательств теорем используются тройные числа пересечений [2].
и матрицу Q дуальных собственных значений
Пусть u, v, w — вершины графа Г, {ijh} =
{ ijh ), [ijh] = [ijh] ■
Положим X = Г2(и), Л = ^2. Тогда Л — регулярный граф степени p22 = 300 на к2 = 325 вершинах.
Лемма 2.1. Пусть d(u,v) = d(u,w) = 2 , d(v,w) = 4 . Тогда выполняются следующие утверждения:
-
[113] = [131] = 2 , [133] = 22;
-
[222] = 277 , [224] = [242] = 23;
-
[313] = [331] = 23 , [315] = [351] = 1 , [333] = 277;
-
[422] = 22 , [424] = [442] = 2;
-
[533] = 1 .
-
<1 Упрощения формул ( * ). >
По лемме 2.1 имеем [222] = 277.
Пусть d(u,v) = 2. Напомним, что p 42 = 300, p 24 = 25, поэтому число ребер между Л(v) и Л 2 (v) в графе Л равно 277 • 25 = 6925.
С другой стороны, указанное число равно 300(299 — А), где А — среднее значение параметра А(Л), поэтому 299 — А = 23.083 и А = 275.917.
Лемма 2.2. Пусть d(u,v) = d(u,w) = d(v,w) = 2 . Тогда выполняются следующие утверждения:
-
[111] = r i — 22 , [113] = [131] = — r i + 24 , [133] = r i ;
-
[222] = —r 1 + 299 , [224] = [242] = r 1 , [244] = —r 1 + 24;
-
[311] = — r i + 24 , [313] = [331] = r i , [333] = — r i + 299 , [335] = [353] = 1;
-
[422] = r i , [424] = [442] = — r i + 24 , [444] = r i — 22;
-
[533] = 1,
где 22 < r i < 24 .
-
< Положив r i = [224] и упростив формулы ( * ) согласно [3], получим требуемые равенства. >
По лемме 2.2 имеем 275 ^ [222] ^ 277.
-
< Доказательство теоремы 1. Пусть d(u, v) = 2. Подсчитаем число f 4 пар вершин y, z на расстоянии 4 в графе X, где y G {24} и z G {2V }. С одной стороны, по лемме 2.1 имеем [224] = 23, поэтому f 4 = 25 • 23 = 575. С другой стороны, по лемме 2.2 имеем [244] = — r i + 24, поэтому f 4 = — £ i r { + 24 • 300 = 575, £ i r { = 6625 и £ i r i /300 = 22.083.
3. Граф с массивом
{
36, 35, 32,4,1; 1, 4, 32, 35, 36
}
Подсчитаем число f 2 пар вершин y, z на расстоянии 2 в графе X, где y G {U4} и z G {Uv }. С одной стороны, по лемме 2.1 имеем [222] = 277, поэтому f 2 = 25 • 277 = 6925. С другой стороны, по лемме 2.2 имеем [242] = r i , поэтому f 4 = i r i i = 6925 и £ i r i /300 = 23.083.
Противоречие с тем, что i r i i /300 = 22.083.
Теорема 1 доказана. >
Пусть Г является дистанционно регулярным графом с массивом пересечений { 36, 35, 32,4,1; 1,4, 32, 35, 36 } . Тогда антиподальное частное — сильно регулярный граф с параметрами (352,36,0,4), половинный граф сильно регулярен с параметрами (352,315,282,280). Далее, Г имеет 1 + 36 + 315 + 315 + 36 + 1 = 704 вершин, спектр: 36 1 ,8 120 ,4 231 , — 4 231 , — 8 120 , - 36 1 , числа пересечений:
Р11 = 0, Р12 = 35, Р22 = 0, Р23 = 280, Р33 = 0, Р34 = 35, Р45 = p211 = 4, p213 = 32, p222 = 282, p224 = 32, p233 = 282, p244 = 4, p235
p 3 12 = 32, p 3 14 = 4, p 3 23 = 282, p 3 33 = 0, p 3 34 = 32, p 3 25 = 1;
p413 = 35, p422 = 280, p424 = 35, p433 = 280, p444 = 0, p415 =1
p 5 14 = 36, p 5 23 = 315,
и матрицу Q дуальных собственных значений
80 3
77 3 11 3 11 3
77 3
77 3 11 3 11 3
77 3
80 3
Пусть u, v, w — вершины графа Г, {ijh} = “VW |, [ijh] = [“^] .
Положим X = Г 2 (и), Л = S 2 . Тогда Л — регулярный граф степени p 22 = 282 на k 2 = 315 вершинах.
Лемма 3.1. Пусть d(u,v) = d(u, w) = 2 , d(v,w) = 4 . Тогда выполняются следующие утверждения:
-
[113] = [131] = 4 , [133] = 28;
-
[222] = 251 , [224] = [242] = 31;
-
[313] = [331] = 31 , [315] = [351] = 1 , [333] = 251;
-
[422] = 28 , [424] = [442] = 4;
-
[533] = 1 .
<1 Упрощения формул ( * ). >
По лемме 3.1 имеем [222] = 251.
Пусть d(u, v) = 2. Напомним, что p 22 = 280, p 24 = 35, поэтому число ребер между Л(v) и Л 2 (v) в графе Л равно 251 • 35 = 8785.
С другой стороны, указанное число равно 280(279 — А), где А — среднее значение параметра А(Л), поэтому 279 — А = 31.375 и А = 247.625.
Лемма 3.2. Пусть d(u, v) = d(u, w) = d(v,w) = 2 . Тогда выполняются следующие утверждения:
-
[111] = r i — 28 , [113] = [131] = — r i + 32 , [133] = r i ;
-
[222] = — r 1 + 281 , [224] = [242] = r 1 , [244] = — r 1 + 32;
-
[311] = — r 1 + 32 , [313] = [331] = r 1 , [333] = — r 1 + 281 , [335] = [353] = 1;
-
[422] = r 1 , [424] = [442] = — r 1 + 32 , [444] = r 1 — 28;
[533] = 1, где 28 C r 1 C 32 .
< Упрощения формул ( * ). >
По лемме 2.2 имеем 249 С [222] С 253.
<1 Доказательство теоремы 2. Пусть d(u, v) = 2. Подсчитаем число f 4 пар вершин y, z на расстоянии 4 в графе X, где y G {U 4} и z € {UV }• С одной стороны, по лемме 3.1 имеем [224] =31, поэтому f 4 = 35 • 31 = 1085. С другой стороны, по лемме 3.2 имеем [244] = - r i +32, поэтому f 4 = - £ i r [ +32 ^ 280 = 1085, £ i r l = 7875 и £ i Г 1 /280 = 28.125.
Подсчитаем число f ? пар вершин y, z на расстоянии 2 в графе X, где y G {U4} и z G {Uv }. С одной стороны, по лемме 3.1 имеем [222] = 251, поэтому f ? = 35 • 251 = 8785. С другой стороны, по лемме 3.2 имеем [242] = r 1 , поэтому f 2 = i r 1 i = 8785 и £ i r i /280 = 31.375.
Противоречие с тем, что i r 1 i / 280 = 28 . 125.
Теорема 2 доказана. >
