Uogólniony wykres Petersena

(6, 2)

.

W teorii grafów uogólnione grafy Petersena to rodzina grafów sześciennych utworzonych przez połączenie wierzchołków wielokąta foremnego z odpowiednimi wierzchołkami wielokąta gwiaździstego . Obejmują one graf Petersena i uogólniają jeden ze sposobów konstruowania grafu Petersena. Uogólniona rodzina grafów Petersena została wprowadzona w 1950 roku przez HSM Coxetera , a jej nazwę nadał jej w 1969 roku Mark Watkins.

Definicja i notacja

W notacji Watkinsa G ( n , k ) jest grafem ze zbiorem wierzchołków

{\ Displaystyle \ {u_ {0}, u_ {1}, \ ldots, u_ {n-1}, v_{0},v_{1},\ldots ,v_{n-1}\}}

i zestaw krawędzi

{\ Displaystyle \ {u_ {i} u_ {i + 1}, u_ {i} v_ {i },v_{i}v_{i+k}\mid 0\równoważnik i\równoważnik n-1\}}

gdzie indeksy dolne mają być odczytywane modulo n i k < n /2. Niektórzy autorzy używają notacji GPG ( n , k ). Notacja Coxetera dla tego samego wykresu to { n } + { n / k }, kombinacja symboli Schläfliego dla regularnego n -kąta i wielokąta gwiazdy , z którego utworzony jest graf. Sam wykres Petersena to G (5, 2) lub {5} + {5/2}.

Każdy uogólniony wykres Petersena można również zbudować z wykresu napięcia z dwoma wierzchołkami, dwiema pętlami własnymi i jedną inną krawędzią.

Przykłady

Wśród uogólnionych grafów Petersena są n -pryzmat G ( n , 1), wykres Dürera G (6, 2), wykres Möbiusa-Kantora G (8, 3), dwunastościan G (10, 2), Desargues wykres G (10, 3) i wykres Nauru G (12, 5).

Cztery uogólnione grafy Petersena – 3-graniastosłupowy, 5-graniastosłupowy, graf Dürera i G (7, 2) – należą do siedmiu grafów sześciennych , połączonych z 3 wierzchołkami i dobrze pokrytych (co oznacza, że wszystkie ich maksymalnych niezależnych zbiorów ma równe rozmiary).

Nieruchomości

Jeden z trzech cykli Hamiltona w G (9, 2). Pozostałe dwa cykle Hamiltona na tym samym wykresie są symetryczne przy obrocie rysunku o 40 °.

Ta rodzina grafów posiada szereg interesujących właściwości. Na przykład:

G ( n , k ) jest wierzchołkowo przechodnia (co oznacza, że ma symetrie, które przenoszą dowolny wierzchołek do dowolnego innego wierzchołka) wtedy i tylko wtedy, gdy ( n , k ) = (10, 2) lub k ² ≡ ±1 (mod n ) .
G ( n , k ) jest przechodnie krawędziowo (mając symetrie, które przenoszą dowolną krawędź na dowolną inną krawędź) tylko w następujących siedmiu przypadkach: ( n , k ) = (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), (24, 5). Te siedem wykresów jest zatem jedynymi symetrycznymi uogólnionymi grafami Petersena.
G ( n , k ) jest dwudzielne wtedy i tylko wtedy, gdy n jest parzyste, a k nieparzyste.
G ( n , k ) jest wykresem Cayleya wtedy i tylko wtedy, gdy k ² ≡ 1 (mod n ).
G ( n , k ) jest hipohamiltonowskie , gdy n jest zgodne z 5 modulo 6 i k = 2, n - 2 lub ( n ± 1)/2 (te cztery wybory k prowadzą do wykresów izomorficznych). Jest również niehamiltonowski , gdy n jest podzielne przez 4, co najmniej równe 8, a k = n /2. We wszystkich innych przypadkach ma cykl Hamiltona . Kiedy n jest przystające do 3 modulo 6 G ( n , 2) ma dokładnie trzy cykle hamiltonowskie. Dla G ( n , 2) liczbę cykli Hamiltona można obliczyć za pomocą wzoru, który zależy od klasy kongruencji n modulo 6 i obejmuje liczby Fibonacciego .
Każdy uogólniony graf Petersena jest wykresem jednostkowej odległości .

izomorfizmy

G ( n , k ) jest izomorficzne z G ( n , l ) wtedy i tylko wtedy, gdy k=l lub kl ≡ ±1 (mod n ).

Obwód

Obwód G ( n , k ) wynosi co najmniej 3 i co najwyżej 8, w szczególności:

{\ Displaystyle g (G (n, k)} \ równoważnik \ min \ lewo \ {8, k + 3, {\ Frac {n} {\ gcd (n, k)}} \ prawo \}.}

Tabela z dokładnymi wartościami obwodów:

Stan	Obwód
${\ displaystyle n = 3k}$	3
${\ displaystyle n = 4k}$	4
${\ displaystyle k = 1}$	4
${\ displaystyle n = 5k}$	5
${\ Displaystyle n = 5k/2}$
${\ Displaystyle k = 2}$
${\ displaystyle n = 6k}$	6
${\ Displaystyle k = 3}$
${\ Displaystyle n = 2k + 2}$
${\ displaystyle n = 7k}$	7
${\ Displaystyle n = 7k/2}$
${\ Displaystyle n = 7k/3}$
${\ Displaystyle k = 4}$
${\ Displaystyle n = 2k + 3}$
${\ Displaystyle n = 3k \ pm 2}$
W przeciwnym razie	8

Liczba chromatyczna i indeks chromatyczny

Będąc regularnymi , zgodnie z twierdzeniem Brooksa ich liczba chromatyczna nie może być większa od ich stopnia . Uogólnione grafy Petersena są sześcienne, więc ich liczba chromatyczna może wynosić 2 lub 3. Dokładniej: