Graf kola - Wheel graph

Graf kola
Několik příkladů grafů kol
Vrcholy	n
Hrany	2(n − 1)
Průměr	2 pokud n > 4 1 pokud n = 4
Obvod	3
Chromatické číslo	4 pokud n je sudý 3 pokud n je zvláštní
Spektrum	${ displaystyle {2 cos (2k pi / (n-1)) ^ {1};}$ ${ displaystyle k = 1, ldots, n-2 }}$${ displaystyle cup {1 pm { sqrt {n}} }}$
Vlastnosti	Hamiltonian Self-dual Rovinný
Zápis	Žn
Tabulka grafů a parametrů

V matematický disciplína teorie grafů, a graf kola je graf vytvořený spojením jediné univerzální vrchol na všechny vrcholy a cyklus. Graf kola s n vrcholy lze také definovat jako 1-kostra z (n-1) -gonal pyramida. Někteří autoři^[1] psát si Ž_n označit graf kola pomocí n vrcholy (n ≥ 4); další autoři^[2] místo toho použijte Ž_n označit graf kola pomocí n+1 vrcholy (n ≥ 3), které jsou tvořeny spojením jednoho vrcholu se všemi vrcholy cyklu délky n. Ve zbytku tohoto článku používáme dřívější notaci.

Konstrukce stavitele

Vzhledem k množině vrcholů {1, 2, 3,…, v} lze sadu okrajů grafu kola reprezentovat v set-builder notace autor: {{1, 2}, {1, 3},…, {1, v}, {2, 3}, {3, 4},…, {v - 1, v}, {v, 2}} .^[3]

Vlastnosti

Grafy kol jsou rovinné grafy, a jako takové mají jedinečné rovinné vložení. Přesněji řečeno, každý graf kola je a Halinův graf. Jsou sebe-duální: planární duální jakéhokoli grafu kola je izomorfní graf. Každý maximální rovinný graf, jiný než K.₄ = Ž₄, obsahuje buď jako podgraf Ž₅ nebo Ž₆.

Vždy existuje Hamiltonovský cyklus v grafu kola a tam jsou ${ displaystyle n ^ {2} -3n + 3}$ cykly v Ž_n (sekvence A002061 v OEIS ).

Sedm cyklů grafu kola Ž₄.

Pro liché hodnoty n, Ž_n je perfektní graf s chromatické číslo 3: vrcholy cyklu mohou mít dvě barvy a střední vrchol třetí barvu. Dokonce i n, Ž_n má chromatické číslo 4 a (když n ≥ 6) není dokonalý. Ž₇ je jediný graf kola, který je a graf jednotkové vzdálenosti v euklidovské rovině.^[4]

The chromatický polynom grafu kola Ž_n je :

${ displaystyle P_ {W_ {n}} (x) = x ((x-2) ^ {(n-1)} - (- 1) ^ {n} (x-2)).}$

v matroid Teorie, dvě obzvláště důležité speciální třídy matroidů jsou kolové matroidy a vířit matroidy, oba odvozené z grafů kol. The k- matroid kola je grafický matroid kola Ž_{k + 1}, zatímco k- vířící matroid je odvozen z k- kolo s ohledem na vnější cyklus kola a na všechny jeho klenout se nad stromy, být nezávislý.

Kolo Ž₆ dodal protiklad k domněnce Paul Erdős na Ramseyova teorie: domníval se, že celý graf má nejmenší Ramseyovo číslo ze všech grafů se stejným chromatickým číslem, ale Faudree a McKay (1993) ukázali Ž₆ má Ramsey číslo 17, zatímco kompletní graf se stejným chromatickým číslem, K.₄, má Ramsey číslo 18.^[5] To znamená pro každý 17-vertexový graf G, buď G nebo jeho doplněk obsahuje Ž₆ jako podgraf, zatímco ani 17-vrchol Paleyův graf ani jeho doplněk neobsahuje kopii K.₄.

Reference