О графах Шилла Г с b2=c2, имеющих собственное значение 2=0
Автор: Махнв А.А., Биткина В.В., Гутнова А.К.
Журнал: Вестник Пермского университета. Математика. Механика. Информатика @vestnik-psu-mmi
Рубрика: Математика
Статья в выпуске: 3 (66), 2024 года.
Бесплатный доступ
Граф Шилла с b2=c2, имеющий собственное значение θ2=0 имеет массив пересечений {b(b+1)s,(bs+s+1)(b-1),bs;1,bs,(b2-1)s}. Из 55 графов с b3+6s2+2s,4s3+4s2+2s,2s2+s;1,2s2+s,4s3+4s2}. В работе изучаются графы Шилла с b2=c2, имеющие собственное значение θ2=0, и массив пересечений {4𝑠3+6𝑠2+2𝑠,4𝑠3+4𝑠2+2𝑠,2𝑠2+𝑠;1,2𝑠2+𝑠,4𝑠3+4𝑠2}.
Блок-схема, дистанционно регулярный граф, граф шилла
Короткий адрес: https://sciup.org/147245560
IDR: 147245560 | DOI: 10.17072/1993-0550-2024-3-16-22
Текст научной статьи О графах Шилла Г с b2=c2, имеющих собственное значение 2=0
CC BY 4.0. Чтобы просмотреть копию этой лицензии, посетите
Рассматриваются неориентированные графы без петель и кратных ребер. Если a, b – вершины графа Γ, то через d(a,b) обозначается расстояние между a и b, а через Γ i (a) – подграф графа Γ, индуцированный множеством вершин, которые находятся на расстоянии i в Γ от вершины a. Подграф Γ 1 (a) называется окрестностью вершины a и обозначается через [а]. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром a.
Граф Γ называется регулярным графом степени k, если [a] содержит точно k вершин для любой вершины a из Γ. Граф Γ называется реберно регулярным графом с параметрами (v,k,λ), если Γ содержит v вершин, является регулярным степени k, и каждое ребро из Γ лежит в λ треугольниках. Граф Γ называется вполне регулярным графом с параметрами (v,k,λ,μ), если Γ реберно регулярен с соответствующими параметрами и подграф [а] А [й] содержит р вершин в случае d(a,b)=2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом . Число вершин в [а] А [й] обозначим через X(a,b) (через p(a,b)), если d(a,b)=1 (если d(a,b)=2), а соответствующий подграф назовем (μ-) λ- подграфом .
Если вершины u, w находятся на расстоянии i в Γ, то через b i (u, w) (через c i (u,w)) обозначим число вершин в пересечении Γ i+1 (u) (в пересечении Γ i-1 (u)) с [w]. Граф диаметра d называется дистанционно регулярным с массивом пересечений {b 0 ,...,b d-1 ;c 1 ,...,c d }, если значения b i =b i (u,w) и c i =c i (u,w) не зависит от выбора вершин u, w на расстоянии i. Положим a i =k-b i -c i и k i =|Γ i (u)| (значение k i не зависит от выбора вершины u). Числа пересечений графа р- и параметры Крейна Q- определены в [1] (стр. 43 и 48 соответственно).
Пусть Г является дистанционно регулярным графом диаметра d. Для i £ {1,2, ^,d} граф r i определен на множестве вершин графа Г и две вершины u, w смежны в Γ i тогда и только тогда, когда d Γ (u,w)=i.
Графом Шилла называется дистанционно регулярный граф диаметра 3 с собственным значением θ 1 =a 3 [2]. Для графа Шилла число a=a 3 делит k и полагают Ь=Ь(Г)=к/а. Граф Шилла имеет массив пересечений {ай, (а + 1)(й-1),Ь2; 1,с2,а(й - 1)}.
Пусть Г является дистанционно регулярным графом диаметра 3 с собственным значением 0 2 =0. Тогда Г имеет массив пересечений {ху + yz,yz — у,ху — х;1,х + z, yz} [3]. Если ху — х = х + z, то z = х(у — 2} и мы имеем двупараметрический массив пересечений {ху + х(у — 2)у, х(у — 2)у — у,ху — х; 1, ху — х, х(у — 2)у}.
Если Г дополнительно является графом Шилла с b 2 =C 2 , то либо 2s + 1 < b — 2, либо Г имеет массив пересечений {4s3 + 6s2 + 2s, 4s3 + 4s2 + 2s, 2s2 + s; 1,2s2 + s, 4s3 + 4s2}.
В работе изучаются графы Шилла Г с b 2 =C 2 и собственным значением 0 2 =0.
Теорема 1. Дистанционно регулярный граф c массивом пересечений {4s3 + 6s2 + 2s, 4s3 + 4s2 + 2s, 2s2 + s; 1,2s2 + s, 4s3 + 4s2} не существует.
1. Тройные числа пересечений
В доказательстве теорем используются тройные числа пересечений [4].
Пусть Г — дистанционно регулярный граф диаметра d . Если u i , и 2 , и з - вершины графа Г, r i , r 2 , r 3 - неотрицательные целые числа, не большие d , то {u 1 u2u3;r 1 r2r3} - множество вершин w £ Г таких, что d(w,U i )=r i , [u 1 u2u3; r 1 r2r3] = \{u 1 u2u3; r 1 r2r3} |. Числа [и 1 и2и3; r 1 r2r3] называются тройными числами пересечений . Для фиксированной тройки вершин и i , и 2 , и з вместо [и 1 и2и3; r 1 r2r3] будем писать [ r 1 r 2 r 3 ].
Пусть и, v, w — вершины графа Г, W = d ( u,v ) , U = d ( v,w ) , V = d ( u,w ). Так как имеется точно одна вершина x = и такая, что d ( х,и )=0, то число [0 jh ] равно 0 или 1. Отсюда [0 jh ]= d jw d hv . Аналогично, [ i 0 h ]= d iw d hu и [ ij 0] = d iu d jv .
Другое множество уравнений можно получить, фиксируя расстояние между двумя вершинами из {u,v,w} и, сосчитав число вершин, находящихся на всех возможных расстояниях от третьей, получим:
hiWh] = p1 ^ — [Qjh], ^[Uh] = P i h — [iQh], ^[ijl] = p ^ — [ijO]. (+)
При этом некоторые тройки исчезают. При |i-j|>W или l+j
Положим S {i jh } (u,v,w) = 'Er.s.t^QriQsjQth [{^Х где Q ij - элементы дуальной матрицы собственных значений Q . Если параметр Крейна q1 } = 0, то S ijh ( u,v,w )=0.
Зафиксируем вершины и, v, w дистанционно регулярного графа Г диаметра 3 и положим {ijh} = {uvw; ijh}, [ijh] = [uvw; ijh], [ijh] ' = [uvw; ihj], [ijh] * = [uvw; jih] и [ijh] ~ = [uvw; hji]. Вычисление [ijh] ' , [ijh] * и [ijh] ~ (симметризация массива тройных чисел пересечений) может дать новые соотношения, позволяющие доказать несуществование графа.
2. Доказательство теоремы 1
В этом разделе Г - дистанционно регулярный граф с массивом пересечений {4s3 + 6s2 + 2s,4s3 + 4s2 + 2s,2s2 + s; 1,2s2 + s,4s3 + 4s2}. Тогда Г имеет 1 + 4s3 + 6s2 + 2s + 4(s + 1)(2s3 + 2s2 + s) + (2s2 + 2s + 1)(2s + 1) вершин, неглавные собственные значения 2(s + 1)s, 0,—(2s2 + 2s + 1) кратностей 4s3 + 8s2 + 4s + 1, 2(4s3 + 8s2 + 4s + 1)s, 4(s + 1)2s и числа пересечений p11 = 2s2 — 1,p12 = 4s3 + 4s2 + 2s, p12 = 8s4 + 8s3 + 4s2, p13 = 4s3 + 4s2 + 2s,p3.3 = 2s2 + 2s + 1;
Р 21 = 2s2 + s, р 2 2 = 4s3 + 2s2,
P23 = 2s2 + s, p22 = 8s4 + 8s3 + 8s2 + 2s — 2, p23 = 4s3 + 2s2 + 2s + 1,p23 = 2s2 + s;
Р32 = 4s3 + 4s2,p33 = 2s2 + 2s, p32 = 8s4 + 8s3 + 4s2 + 4s, p33 = 4s3 + 4s2,p|3 = 2s.
Пусть u, v, w — вершины графа Г, {rst} = {uvw; rst} и [rst] = [uvw; rst]. Положим Е=Г з (и), Л=^ 2 . Тогда Л является регулярным графом степени р 3 3 = 4s3 + 4s2 на к3 = (2s2 + 2s + 1)(2s + 1) вершинах.
Лемма 1. Пусть d(u,v)=d(u,w)=3, d(v,w)=1. Тогда выполняются следующие утверждения:
-
[122] = r 14 ,
-
[123] = [132] = 4s3 + 4s2 — r14,
-
[133] = —4s 3 — 2s2 + 2s + Г 14 ;
-
[211] =Г 12 ,
-
[212] = [221] = 4s3 + 4s2 — r12,
-
[222] = 8s4 + 4s3 + 2s + r12 + r13 — r14,
-
[223] = [232] = 2s —r13 +r14,
-
[233] = 4s3 + 4s2 — 2s + r13 — r14;
-
[311] = 2s2 — 1 — r 12 , [312] = [321] = 2s + r 12 ,
-
[322] = 4s3 + 4s2 — 2s — r12 — r13,
-
[323] = [332] = r13, [333] = 2s — r13,
где r13 < 2s, r12 < 2s2 — 1, 4s3 + 2s2 — 2s < r14 < 4s3 + 4s2.
Доказательство. Упрощения формул (+).
По лемме 1 имеем [322] = 4s3 + 4s2 —2s — r12 — r13 < 4s3 + 4s2 — 2s.
Так как {u, w} U Л(и) U A(w) содержит 2 + 8s3 + 8s2 — [322] вершин, то 4s3 + 2s2 — 4s + 1 < [322] < 4s3 + 4s2 — 2s.
Лемма 2. Пусть d(u,v)=d(u,w)=d(v,w)=3. Тогда выполняются следующие утверждения:
-
[122] = 4s3 + 4s2 — r36,
-
[123] = [132] = r36, [133] = 2s2 + 2s — r36;
-
[212] = 4s3 + 2s2 — 1 — r34 — r37,
-
[213] = 2s2 + 1 + r 34 + r 37 , [221] = r 3 5,
-
[222] = 8s4 + 4s3 + 4s + r34 — r35 + r36,
-
[223] = 4s3 + 4s2 — r34 — r36,
-
[231] = 4s3 + 4s2 — r35,
-
[232] = 2s2 + 1 + r 3 5 — r 36 + r 37 ,
-
[233] = —2s 2 — 1 + r 36 — r 37 ;
-
[312] = 2s2 + 1 + r34 + r37,
-
[313] = 2s — 1 — Г 34 — Г 37 , [321] = 4s3 + 4s 2 — Г 35 ,
-
[322] = —Т 34 + т 35 ,[323]=Т 34 ,
-
[332] = 4s3 + 2s2 — 1 — Г з 5 — Г з7 ,
-
[333] = Г 37 , где r36< 2s2 + 2s, r35 + r37< 4s3 + 2s2 — 1,r35< 4s3 + 4s2,r34 + r37< 2s — 1. Доказательство. Упрощения формул (+).
По лемме 2 имеем [322] = —r34 + r35 < 4s3 + 2s2 — 1. Как и выше, 4s3 + 2s2—4s + 1< [322].
Найдем число ребер d между Л(v) и Л 2 (у). Так как р 3 3 = 2s2 + 2s, р 3 3 = 4s3 + 4s2,p f 3 = 2s, то (2s2 + 4s)(4s3 + 2s2 — 4s + 1) < d < (2s2 + 2s)(4s3 + 4s2 —
2s) + 2s(4s3 + 2s2 — 1). С другой стороны, d = (4s3 + 4s2)(4s3 + 4s2 — 1 — 2), поэтому (2s2 + 4s)(4s3 + 2s2 — 4s + 1) < (4s3 + 4s2)(4s3 + 4s2 — 1 — 2) <
2s((s + 1)(4s3 + 4s2 — 2s) + (4s3 + 2s2 — 1)), (s2 + 2)(4s3 + 2s2 — 4s + 1)/ (2s2 + 2s) < 4s3 + 4s2 — 1 — 2 < (4s4 + 12s3 + 4s2 — 2s — 1)/(2s2 + 2s) и 4s3 + 4s2 — 1 — (s2 + 2)(4s3 + 2s2 — 4s + 1)/(2s2 + 2s) < 2 < 4s3 + 4s2 — 1 — (4s4 + 12s3 + 4s2 — 2s — 1)/(2s2 + 2s), где λ – среднее значение параметра λ(Λ).
Лемма 3. Пусть d(u,v)=d(u,w)=3,d(v,w)=2. Тогда выполняются следующие утверждения:
-
[121] = 4s3 + 2s2 — r 23 — r 24 + r 25 ,
-
[122] = —s + r 23 + r 24 — r 25 + r 27 ,
-
[123] = 2s2 + s — r27,
-
[131] = —4s3 + s + r 23 + r 24 — r 25 ,
-
[132] = 4s3 + 2s2 + s — r 23 — r 24 + r 25 + Т 27 ,
-
[133] = т 27 ;
-
[211] = r24, [212] = 4s3 + 2s2 — s — r24 + r28,
-
[213] = 2s2+s —r 28 , [221] =r 23 ,
-
[222] = 8s4 + 4s3 + 6s2 + 3s — 2 + r24 — r26 — r28,
-
[223] = 4s3 — 2s2 + s + 1 — r 23 — r 24 + r 26 + r 28 ,
-
[231] = 4s3 + 2s2 — r 23 — r 24 ,
-
[232] = r 26 , [233] = 2s2 + Т 23 + Т 24 — Т 26 ;
-
[311] = 2s2 + s — r 24 , [312] = s + r 24 — r 28 ,
-
[313] =r 28 ,[321] =r 24 —r 2 5,
-
[322] = 4s3 + 2s2 — r 23 — 2Т 24 + r 25 + r 26 — r 27 + r 28 ,
-
[323] = 2s2 + r 23 + r 24 — r 26 + r 27 — r 28 ,
-
[331] = r 25 , [332] = s + r 23 + r 24 — r 25 — r 26 + r 27 , [333] = s — r 23 — r 24 + r 26 — r 27 ,
где Т 24 ,Т 27 ,Т 28 < 2s 2 + s,T 23 + r 24 < 4s3 + 2s2,T 25 < r 24 .
Доказательство. Упрощения формул (+).
По лемме 3 имеем [322] = 4s3 + 2s2 — r23 — 2r24 + r25 + r26 — r27 + r28. Как и выше, 4s3 + 2s2 — 4s — 1 < [322].
Симметризация [133] = r27 = r2‘7, [211] = r24 = r2‘4, [212] = 4s3 + 2s2 — s — r24 + r28 = [221]‘ = r23, поэтому 4s3 + 2s2 — s = Т24 — r28 + r'3.
Пусть d(u,v)=3.
Подсчитаем число f i пар вершин y, z на расстоянии 1 в графе Г, где у Е {uv; 31} и z Е {uv; 32}. С одной стороны, по лемме 1 имеем [321] = 2s + r12, где r12< 2s2 — 1, поэтому 2s(2s2 + 2s) < f 1 < (2s2 + 2s)(2s2 + 2s — 1).
С другой стороны, по лемме 3 имеем [311] = 2s2 + s — r24, поэтому 2s(2s2 + 2s) < f 1 = — Yir24 + p 3 3(2s2 + s) < (2s2 + 2s)(2s2 + 2s — 1), p 3 3(2s2 + s) —
(2s2 + 2s)(2s2 + 2s — 1) < Zir2i4< p 3 3(2s2 + s) — 2s(2s2 + 2s) и 2s2 + s — (2s2 + 2s — 1)/(4s3 + 2s2 — 4s + 1) < Eir2i4/p 3 3< 2s2 + s — 2s/(4s3 + 2s2— 4s + 1).
Подсчитаем число f 2 пар вершин y, z на расстоянии 2 в графе Г, где у Е {uv; 31} и z Е {uv; 32}. С одной стороны, по лемме 1 имеем 4s3 + 2s2 — 4s + 1 < [322] < 4s3 + 4s2 — 2s, поэтому (2s2 + 2s)(4s3 + 2s2 — 4s + 1) < f2< (2s2 + 2s)(4s3 + 4s2 — 2s). С другой стороны, по лемме 3 имеем [312] = s + r24 — r28, поэтому (2s2 + 2s)(4s3 + 2s2 — 4s + 1) < f2 = £i(r2i4 — r28) + p 3 3 s < (2s2 + 2s)(4s3 + 4s2 — 2s), —p 3 3 s + (2s2 + 2s)(4s3 + 2s2 — 4s + 1) < ^(r^ — r^) < —p 3 3 s +
(2s2 + 2s)(4s3 + 4s2 — 2s) и —s + 1 < Ei(r2i4 — r^) /p 3 3< —s + (4s3 + 4s2 — 2s)/(4s3 + 2s2 — 4s + 1).
Отсюда s — (4s3 + 4s2 — 2s)/(4s3 + 2s2 — 4s + 1) < Zi(r2i8 — r24) /p 3 3< s — 1.
Подсчитаем число f a пар вершин y, z на расстоянии 3 в графе Г, где у Е {uv; 31} и z Е {uv; 32}. С одной стороны, по лемме 1 имеем [323] = r34, где r34< 2s — 1, поэтому 0 < f3< (2s2 + 2s)(2s — 1). С другой стороны, по лемме 3 имеем [313] = r 28 , поэтому 0< f1 = X i r 28 < (2s2 + 2s)(2s — 1) и S i r2 8 /((2s2 + 2s)(4s3 + 2s2 — 4s + 1)) < (2s — 1)/(4s3 + 2s2 — 4s + 1).
Таким образом, s — (4s3 + 4s2 — 2s)/(4s3 + 2s2 — 4s + 1) < Si(r2i8 — r24) / p 3 3< (2s — 1)/(4s3 + 2s2 — 4s + 1) и s = 1.
Теорема 1 доказана.
Список литературы О графах Шилла Г с b2=c2, имеющих собственное значение 2=0
- Brouwer A.E., Cohen A.N., Neumaier A. Distance-Regular Graphs // Springer-Verlag. Berlin Heidelberg New-York, 1989.
- Koolen J, Park J. Shilla distance-regular graphs // Europ. J. Comb. 31, 2064-2073, 2010.
- Makhnev A.A., Belousov I.N. On distance-regular graphs of diameter 3 with eigenvalue // Trudy Institute Math. (Novosibirsk). 33, № 1, 162-173, 2022.
- Coolsaet K., Juriˇsi'c A. Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs // J. Comb. Theory, Series A. 2008. Vol. 115. 1086-1095.