Příklady grafů kola | |
---|---|
Vrcholy | n |
žebra | 2( n − 1) |
Průměr |
2 pro n>4 1 pro n =4 |
obvod | 3 |
Chromatické číslo | 3 pro liché n , 4 pro sudé n |
Vlastnosti |
Hamiltonovská duální rovina |
Označení | W n |
Mediální soubory na Wikimedia Commons |
V teorii grafů je kolo W n graf s n vrcholy (n ≥ 4), vytvořený spojením jediného vrcholu se všemi vrcholy cyklu ( n -1 ) . Číselné označení kol v literatuře není zavedené - někteří autoři používají n pro označení délky cyklu, takže jejich W n znamená graf W n+1 definovaný výše [1] . Kolo lze definovat stejným způsobem jako 1-skelet( n -1)-uhelná pyramida .
Nechť je dána množina vrcholů {1,2,3,…,v}. Množina hran grafového kola může být reprezentována jako množina {{1,2},{1,3},…,{1,v},{2,3},{3,4},…, {v-1, v},{v,2}} [2] .
Kolečka jsou rovinné grafy , a proto mají jedinečné zapuštění do roviny. Jakékoli kolo je Halinův graf . Jsou autoduální — duální graf jakéhokoli kola je izomorfní s kolem samotným. Jakýkoli maximální rovinný graf jiný než K 4 = W 4 obsahuje buď W 5 nebo W 6 jako podgraf .
V kole je vždy hamiltonovský cyklus a počet cyklů ve W n je (sekvence A002061 v OEIS ).
7 cyklů v kole W 4 . |
Pro liché hodnoty n je W n dokonalý graf s chromatickým číslem 3 – vrcholy cyklu mohou být obarveny dvěma barvami a centrální vrchol bude mít třetí barvu. Pro sudé n W n má kolo chromatické číslo 4 a (pro n ≥ 6) nebude dokonalý graf. W 7 je jediné kolo, které je grafem jednotkové vzdálenosti na euklidovské rovině [3] .
Chromatický polynom kola W n je:
V teorii matroidů existují dva zvláště důležité druhy matroidů, kola a víry , z nichž oba jsou odvozeny z kolových grafů. Matroid k -wheel je grafový matroidkolo W k+1 a k -vírový matroid se získá z matroidu k -kola tím, že vnější cyklus (ráfek) je nezávislý jako jeho kostry .
Kolečko W 6 poskytuje protipříklad k domněnce Paula Erdőse v Ramseyho teorii – předpokládal, že úplný graf má nejmenší Ramseyovo číslo ze všech grafů se stejným chromatickým číslem. Faudree a McKay (Faudree, McKay, 1993) však ukázali, že pro W 6 je Ramseyovo číslo 17, zatímco pro úplný graf K 4 se stejným chromatickým číslem je Ramseyovo číslo 18 [4] . Pro jakýkoli 17-vrcholový graf G tedy buď G samotný nebo jeho doplněk obsahuje W 6 jako podgraf, zatímco Paleyův graf se 17 vrcholy ani jeho doplněk neobsahují K 4 .