О графах Шилла Г с 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+jW = 0, поэтому [ijh]=0 для всех he{0,_,d}.

Положим 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.
Статья научная