Kolo (teorie grafů)

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 .

Nastavení reprezentace

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] .

Vlastnosti

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 ).

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 .

Poznámky

1. ↑ Weisstein, Eric W. Wheel Graph  na webu Wolfram MathWorld .
2. ↑ Richard J. Trudeau. Úvod do teorie grafů. — Opravená, rozšířená republika. New York: Dover Pub. - S. 56. - ISBN 978-0-486-67870-2 .
3. ↑ Fred Buckley, Frank Harary. O euklidovské dimenzi kola // Grafy a kombinatorika. - 1988. - V. 4 , čís. 1 . — S. 23–30 . - doi : 10.1007/BF01864150 .
4. ↑ Ralph J. Faudree, Brendan D. McKay. Erdősova domněnka a Ramseyho číslo r ( W 6 ) // J. Kombinatorická matematika. a kombinační výpočet. - 1993. - T. 13 . — S. 23–31 .