Klatka (teoria grafów) - Cage (graph theory)

Tutte (3,8) -cage .

W matematycznej dziedzinie teorii grafów , A klatka jest graf regularny , który ma za kilka wierzchołków , jak to możliwe na jej obwodzie .

Formalnie, ( r , g ) -graph definiuje się jako graf, na którym każdy wierzchołek ma dokładnie r sąsiadów i w którym najkrótszy cykl ma długość dokładnie g . Klatka ( r , g ) jest grafem ( r , g ) z najmniejszą możliwą liczbą wierzchołków spośród wszystkich ( r , g ) -grafów. A (3 g ) -cage jest często nazywany g -cage.

Wiadomo, że ( r , g ) -graf istnieje dla dowolnej kombinacji r ≥ 2 i g ≥ 3. Wynika z tego, że istnieją wszystkie ( r , g ) -klatki.

Jeśli istnieje wykres Moore'a ze stopniem r i obwodem g , musi to być klatka. Ponadto granice rozmiarów wykresów Moore'a uogólniają się na klatki: każda klatka o nieparzystym obwodzie g musi mieć co najmniej

wierzchołki, a każda klatka o równym obwodzie g musi mieć co najmniej

wierzchołki. Każdy ( r , g ) -graf z dokładnie taką liczbą wierzchołków jest z definicji grafem Moore'a, a zatem automatycznie klatką.

Może istnieć wiele klatek dla danej kombinacji r i g . Na przykład istnieją trzy nieizomorficzne (3,10) klatki, z których każda ma 70 wierzchołków: 10-klatkowa Balaban , wykres Harriesa i wykres Harriesa-Wonga . Ale jest tylko jedna (3,11) -klatka: 11-klatka Balaban (ze 112 wierzchołkami).

Znane klatki

1-regularny graf nie ma cyklu, a połączony 2-regularny graf ma obwód równy liczbie wierzchołków, więc klatki są interesujące tylko dla r ≥ 3. Klatka ( r , 3) jest kompletnym grafem K r +1 na r +1 wierzchołkach, a ( r , 4) -klatka jest kompletnym dwudzielnym grafem K r , r na 2 r wierzchołkach.

Godne uwagi klatki obejmują:

Liczby wierzchołków w znanych ( r , g ) klatkach, dla wartości r > 2 i g > 2, innych niż płaszczyzny rzutowe i uogólnione wielokąty, są następujące:

sol
r
3 4 5 6 7 8 9 10 11 12
3 4 6 10 14 24 30 58 70 112 126
4 5 8 19 26 67 80 728
5 6 10 30 42 170 2730
6 7 12 40 62 312 7812
7 8 14 50 90

Asymptotyki

Dla dużych wartości g , ograniczenie Moore'a oznacza, że ​​liczba n wierzchołków musi rosnąć co najmniej pojedynczo wykładniczo w funkcji g . Równoważnie g może być co najwyżej proporcjonalne do logarytmu o n . Dokładniej,

Uważa się, że ta granica jest ścisła lub bliska ( Bollobás i Szemerédi 2002 ). Najbardziej znane dolne granice g są również logarytmiczne, ale z mniejszym stałym współczynnikiem (co oznacza, że n rośnie pojedynczo wykładniczo, ale w tempie wyższym niż granica Moore'a). W szczególności konstrukcja grafów Ramanujana zdefiniowana przez Lubotzky'ego, Phillipsa i Sarnaka (1988) spełnia

Ta granica została nieco poprawiona przez Lazebnika, Ustimenko i Woldara (1995) .

Jest mało prawdopodobne, że te grafy same w sobie są klatkami, ale ich istnienie wyznacza górną granicę liczby wierzchołków potrzebnych w klatce.

Bibliografia

Linki zewnętrzne