Wykres silnie regularny - Strongly regular graph

Paley wykres porządku 13, silnie regularny wykres z parametrów SRG (13,6,2,3).

W teorii grafów , o silnie graf regularny jest zdefiniowana w następujący sposób. Niech G = ( V , E ) będzie grafem regularnym o wierzchołkach v i stopniu k . Mówi się, że G jest silnie regularne, jeśli istnieją również liczby całkowite λ i μ takie, że:

• Co dwa sąsiednie wierzchołki mają wspólnych sąsiadów λ.
• Każde dwa niesąsiadujące wierzchołki mają wspólnych sąsiadów μ.

Czasami mówi się, że wykres tego rodzaju jest srg( v , k , λ, μ). Bardzo regularne wykresy zostały wprowadzone przez RC Bose w 1963 roku.

Niektórzy autorzy wykluczają grafy, które spełniają definicję w trywialny sposób, a mianowicie te grafy, które są rozłączną sumą jednego lub więcej kompletnych grafów o jednakowej wielkości , oraz ich uzupełnień , kompletnych grafów wieloczęściowych o równych rozmiarach niezależnych zbiorów.

Uzupełnieniem o SRG ( v , k , λ, u) jest również silnie regularny. Jest to srg( v , v−k -1, v -2−2 k +μ, v -2 k +λ).

Wyraźnie regularny wykres to wykres z regularnością odległości o średnicy 2, gdy μ jest niezerowe. Jest to graf lokalnie liniowy, gdy λ=1.

Nieruchomości

Związek między parametrami

Cztery parametry w srg( v , k , λ, μ) nie są niezależne i muszą być zgodne z następującą zależnością:

${\ Displaystyle (vk-1) \ mu = k (k-\ lambda -1)}$

Powyższy związek można bardzo łatwo wyprowadzić za pomocą argumentu zliczania w następujący sposób:

1. Wyobraź sobie, że wierzchołki wykresu leżą na trzech poziomach. Wybierz dowolny wierzchołek jako pierwiastek na poziomie 0. Następnie jego k sąsiedzi leżą na poziomie 1, a wszystkie inne wierzchołki leżą na poziomie 2.
2. Wierzchołki na poziomie 1 są bezpośrednio połączone z pierwiastkiem, dlatego muszą mieć λ innych wspólnych sąsiadów z pierwiastkiem, a ci wspólni sąsiedzi również muszą znajdować się na poziomie 1. Ponieważ każdy wierzchołek ma stopień k , dla każdego poziomu 1 pozostają krawędzie węzeł do połączenia z węzłami na poziomie 2. Dlatego istnieją krawędzie między poziomem 1 a poziomem 2.${\ Displaystyle k-\ lambda -1}$${\ Displaystyle k \ razy (k-\ lambda -1)}$
3. Wierzchołki na poziomie 2 nie są bezpośrednio połączone z korzeniem, dlatego muszą mieć wspólnych sąsiadów μ z korzeniem, a wszyscy ci wspólni sąsiedzi muszą znajdować się na poziomie 1. Na poziomie 2 są wierzchołki, a każdy z nich jest połączony z węzłami μ na poziomie 1. Dlatego liczba krawędzi między poziomem 1 a poziomem 2 wynosi .${\ Displaystyle (vk-1)}$${\ Displaystyle (vk-1) \ razy \ mu}$
4. Po zrównaniu dwóch wyrażeń dla krawędzi między Poziomem 1 i Poziomem 2, relacja jest następująca.

Macierz sąsiedztwa

Niech I oznaczają macierz tożsamości i pozwolić J oznaczają matrycy te , zarówno matryce rzędu v . Macierz sąsiedztwa z silnie regularnych wykresu spełnia dwa równania. Pierwszy:

${\displaystyle AJ=JA=kJ}$

co jest trywialnym powtórzeniem wymogu regularności. To pokazuje, że k jest wartością własną macierzy sąsiedztwa z wektorem własnym składającym się z samych jedynek. Drugie to równanie kwadratowe,

${\ Displaystyle {A} ^ {2} = k {I} + \ lambda {A} + \ mu ({JIA})}$

co wyraża silną regularność. Przez IJ -ty element po lewej stronie daje liczbę ścieżek dwustopniowe od I do j . Pierwszy składnik RHS podaje liczbę samodzielnych ścieżek od i do i , a mianowicie k odchodzi i wraca do środka. Drugi składnik podaje liczbę dwustopniowych ścieżek, gdy i oraz j są bezpośrednio połączone. Trzeci wyraz daje odpowiednią wartość, gdy i i j nie są połączone. Ponieważ te trzy przypadki wzajemnie się wykluczają i zbiorowo wyczerpują się , następuje prosta równość addytywna.

I odwrotnie, graf, którego macierz sąsiedztwa spełnia oba powyższe warunki i który nie jest grafem kompletnym lub zerowym, jest grafem silnie regularnym.

Wartości własne

Macierz sąsiedztwa wykresu ma dokładnie trzy wartości własne :

• k , którego krotność wynosi 1 (jak widać powyżej)
• ${\ Displaystyle {\ Frac {1} {2}} \ lewo [(\ lambda - \ mu) + {\ sqrt {(\ lambda - \ mu) ^ {2} + 4 (k-\ mu)}} \ ,\dobrze],}$ którego wielość jest ${\ Displaystyle {\ Frac {1} {2}} \ lewo [(v-1) - {\ Frac {2k + (V-1) (\ lambda - \ mu)} {\ sqrt {(\ lambda - \ mu )^{2}+4(k-\mu )}}}\prawo]}$
• ${\ Displaystyle {\ Frac {1} {2}} \ lewo [(\ lambda - \ mu) - {\ sqrt {(\ lambda - \ mu) ^ {2} + 4 (k-\ mu)}} \ ,\dobrze],}$ którego wielość jest ${\ Displaystyle {\ Frac {1} {2}} \ lewo [(v-1) + {\ Frac {2k + (V-1) (\ lambda - \ mu)} {\ sqrt {(\ lambda - \ mu )^{2}+4(k-\mu )}}}\prawo]}$

Ponieważ krotności muszą być liczbami całkowitymi, ich wyrażenia zapewniają dalsze ograniczenia wartości v , k , μ i λ , związane z tak zwanymi warunkami Kerina .

Wykresy silnie regularne, dla których mają wartości własne całkowite o nierównych krotnościach. ${\ Displaystyle 2k + (v-1) (\ lambda - \ mu) \ neq 0}$

Grafy silnie regularne, dla których nazywane są grafami konferencyjnymi ze względu na ich połączenie z symetrycznymi matrycami konferencyjnymi . Ich parametry zmniejszają się do ${\ Displaystyle 2k + (v-1) (\ lambda - \ mu) = 0}$

${\ Displaystyle {\ tekst {srg}} {\ duży (} v {\ tfrac {1} {2}} (v-1), {\ tfrac {1} {4}} (v-5), { \tfrac {1}{4}}(v-1){\big )}.}$

Odwrotnie, połączony graf regularny z tylko trzema wartościami własnymi jest silnie regularny.

Przykłady

• Cykl długości 5 jest SRG (5, 2, 0, 1).
• Wykres Petersen jest SRG (10, 3, 0, 1).
• Wykres Clebsch jest SRG (16, 5, 0, 2).
• Wykres Shrikhande jest SRG (16, 6, 2, 2), które nie jest wykres na odległość przechodnia .
• N  x  n square wykres gawroni , czyli wykres liniowy wykres pełnej zrównoważony dwuczęściowego K _{n, n} , jest SRG ( n ² , 2 n  - 2, n  - 2, 2). Parametry dla n =4 pokrywają się z parametrami wykresu Shrikhande, ale oba wykresy nie są izomorficzne.
• Wykres liniowy kompletnego wykres K _n to SRG ( ).${\displaystyle {\binom {n}{2}},2(n-2),n-2,4}$
• Te wykresy Chang są SRG (28, 12, 6, 4), tak samo jak na wykresie linii K ₈ , a te cztery wykresy nie są izomorficzne.
• Wykresem liniowym z uogólnionego czworokąta GQ (2, 4) jest SRG (27, 10, 1, 5). W rzeczywistości każdy uogólniony czworokąt porządku (s, t) daje silnie regularny wykres w następujący sposób: srg((s+1)(st+1), s(t+1), s-1, t +1).
• Wykres Schläfli jest SRG (27, 16, 10, 8).
• Wykres Hoffman Singleton jest SRG (50, 7, 0, 1).
• Wykres Sims-Gewirtz jest (56, 10, 0, 2).
• Wykres M22 vel Mesner wykresu jest SRG (77, 16, 0, 4).
• Wykres Brouwer-Haemers jest SRG (81, 20, 1, 6).
• Wykres Higman-Sims jest SRG (100, 22, 0, 6).
• Wykres lokalny McLaughlin jest SRG (162, 56, 10, 24).
• Wykres Cameron jest SRG (231, 30, 9, 3).
• Berlekamp-Van Lint-Seidel wykres jest SRG (243, 22, 1, 2).
• Wykres McLaughlin jest SRG (275, 112, 30, 56).
• Paley wykres kolejnością q jest takie SRG ( q , ( q  - 1) / 2 ( Q  - 5/4), ( q  - 1) / 4,). Najmniejszy wykres Paley'a, z q = 5, to 5-cykl (powyżej).
• grafy samouzupełniające się łukowo-przechodnie są silnie regularne.

Graf silnie regularny nazywany jest grafem pierwotnym, jeśli zarówno graf, jak i jego dopełnienie są połączone. Wszystkie powyższe wykresy są prymitywne, w przeciwnym razie μ=0 lub λ=k.

Problem 99- grafowy Conwaya wymaga skonstruowania srg(99,14,1,2). Nie wiadomo, czy istnieje wykres z tymi parametrami, a John Horton Conway zaoferował nagrodę w wysokości 1000 USD za rozwiązanie tego problemu.

Wykresy bez trójkątów, wykresy Moore'a i wykresy geodezyjne

Silnie regularne wykresy z λ = 0 są wolne od trójkątów . Oprócz kompletnych grafów na mniej niż 3 wierzchołkach i wszystkich kompletnych grafów dwudzielnych, siedem wymienionych powyżej (pentagon, Petersen, Clebsch, Hoffman-Singleton, Gewirtz, Mesner-M22 i Higman-Sims) są jedynymi znanymi. Silnie regularne wykresy z λ = 0 i μ = 1 to wykresy Moore'a z obwodem 5. Ponownie trzy wykresy podane powyżej (pięciokąt, Petersen i Hoffman-Singleton), z parametrami (5, 2, 0, 1), (10, 3, 0, 1) i (50, 7, 0, 1) to jedyne znane. Jedynym innym możliwym zestawem parametrów dającym wykres Moore'a jest (3250, 57, 0, 1); nie wiadomo, czy taki wykres istnieje, a jeśli tak, to czy jest unikalny.

Mówiąc bardziej ogólnie, każdy silnie regularny graf jest grafem geodezyjnym , grafem , w którym każde dwa wierzchołki mają unikalną nieważoną najkrótszą ścieżkę . Jedynymi znanymi silnie regularnymi grafami są grafy Moore'a. Nie jest możliwe, aby taki wykres posiadał , ale inne kombinacje parametrów, takie jak (400, 21, 2, 1) nie zostały jeszcze wykluczone. Pomimo trwających badań nad właściwościami, które miałby silnie regularny graf , nie wiadomo, czy istnieją, a nawet czy ich liczba jest skończona. ${\ Displaystyle \ mu = 1}$${\ Displaystyle \ mu = 1}$${\ Displaystyle \ lambda =1}$${\ Displaystyle \ mu = 1}$

Zobacz też

• Częściowa geometria
• Macierz sąsiedztwa Seidela
• Dwuwykresowy

Uwagi

Bibliografia

• AE Brouwer, AM Cohen i A. Neumaier (1989), Wykresy odległości regularnych . Berlin, Nowy Jork: Springer-Verlag. ISBN  3-540-50619-5 , ISBN  0-387-50619-5
• Chris Godsil i Gordon Royle (2004), Teoria grafów algebraicznych . Nowy Jork: Springer-Verlag. ISBN  0-387-95241-1

Linki zewnętrzne

• Eric W. Weisstein , artykuł Mathworld z licznymi przykładami.
• Gordon Royle , Lista większych wykresów i rodzin.
• Andries E. Brouwer , Parametry silnie regularnych wykresów.
• Brendan McKay , Niektóre zbiory wykresów.
• Ted Spence , Silnie regularne wykresy na co najwyżej 64 wierzchołkach.