Graf koła
Jak zdefiniowano w tej pracy, graf kołowy rzędu , czasami nazywany po prostu kołem (Harary 1994, s. 46; Pemmaraju i Skiena 2003, s. 248; Tutte 2005, s. 78), jest grafem, który zawiera cykl rzędu i dla którego każdy wierzchołek grafu w cyklu jest połączony z jednym innym wierzchołkiem grafu zwanym piastą. Krawędzie koła, które obejmują piastę, nazywamy szprychami (Skiena 1990, s. 146). Koło może być zdefiniowane jako graf połączony , gdzie jest grafem singletonowym, a jest grafem cyklu, co czyni go grafem stożkowym.
Zauważ, że istnieją dwie konwencje indeksowania dla grafów kołowych, przy czym niektórzy autorzy (np., Gallian 2007), przyjmują konwencję, że oznacza graf kołowy na węzłach.
Graf tetraedryczny (tj. ) jest izomorficzny do , a jest izomorficzny do kompletnego grafu trójdzielnego . W ogólności, graf kołowy jest szkieletem piramidy.
jest jednym z dwóch grafów otrzymanych przez usunięcie dwóch krawędzi z grafu pentatopowego , drugim jest graf domu X.
Grafy kołowe są wdzięczne (Frucht 1979).
Graf kołowy ma wymiar grafu 2 dla (a więc jest jednostkowy) i wymiar 3 w pozostałych przypadkach (a więc nie jest jednostkowy) (Erdős et al. 1965, Buckley i Harary 1988).
Dowolny graf kołowy jest grafem samodualnym.
Grafy kołowe można skonstruować w języku Wolfram Language za pomocą WheelGraph. Wstępnie obliczone własności pewnej liczby grafów kołowych są dostępne za pomocą GraphData.
Liczba cykli grafu w grafie kołowym jest dana przez , lub 7, 13, 21, 31, 43, 57, … (OEIS A002061) dla , 5, ….
W grafie kołowym piasta ma stopień , a pozostałe węzły mają stopień 3. Grafy kołowe są 3-połączone. , gdzie jest grafem zupełnym czwartego rzędu. Liczba chromatyczna grafu wynosi
(1)
|
Graf kołowy ma stopień . graf kołowy ma wielomian chromatyczny
(2)
|
.