Hjul (grafteori)

I grafteorin är ett hjul W n en graf med n hörn (n ≥ 4), bildad av kopplingen av en enda vertex med alla hörn i ( n -1) -cykeln . Den numeriska beteckningen av hjulen i litteraturen är inte väl etablerad - vissa författare använder n för att beteckna cykelns längd, så deras W n betyder grafen W n+1 enligt definitionen ovan [1] . Ett hjul kan definieras på samma sätt som ett 1-skelett( n - 1)-kolpyramid .

Ange representation

Låt uppsättningen av hörn {1,2,3,...,v} ges. Uppsättningen av kanter på grafhjulet kan representeras som en uppsättning {{1,2},{1,3},...,{1,v},{2,3},{3,4},..., {v-1, v},{v,2}} [2] .

Egenskaper

Hjulen är plana grafer och har därför en unik inbäddning i planet. Alla hjul är en Halin-graf . De är självdubbla - den dubbla grafen för alla hjul är isomorf till själva hjulet. Alla maximala plana grafer förutom K 4 = W 4 innehåller antingen W 5 eller W 6 som en subgraf .

Det finns alltid en Hamilton-cykel i hjulet och antalet cykler i W n är (sekvens A002061 i OEIS ).

För udda värden på n är W n en perfekt graf med kromatisk nummer 3 - cykelns hörn kan färgas i två färger, och den centrala vertexen kommer att ha en tredje färg. För även n W n har hjulet kromatiskt nummer 4 och (för n ≥ 6) kommer inte att vara en perfekt graf. W 7 är det enda hjulet som är en enhetsdistansgraf på det euklidiska planet [3] .

Det kromatiska polynomet för hjulet W n är:

Det finns två särskilt viktiga typer av matroider i matroideorin, hjul och virvlar , som båda är härledda från hjuldiagram. K - hjulsmatroiden är en grafmatroidhjul Wk +1 , och k -virvelmatroiden erhålls från k -hjulsmatroiden genom att förklara den yttre cykeln (fälgen) lika oberoende som dess spännande träd .

W 6 - hjulet ger ett motexempel till Paul Erdős gissningar i Ramsey-teorin - han antog att en komplett graf har det minsta Ramsey-talet av alla grafer med samma kromatiska tal. Faudree och McKay (Faudree, McKay, 1993) visade dock att för W 6 är Ramsey-talet 17, medan för en komplett graf K 4 med samma kromatiska tal är Ramsey-talet 18 [4] . Sålunda, för vilken 17-vertex- graf G som helst, innehåller antingen G själv eller dess komplement W6 som en subgraf , medan varken 17-vertex Paley-grafen eller dess komplement innehåller K4 .

Anteckningar

1. ↑ Weisstein, Eric W. Wheel Graph  på Wolfram MathWorld- webbplatsen .
2. ↑ Richard J. Trudeau. Introduktion till grafteori. — Rättad, förstorad republicering. New York: Dover Pub. - S. 56. - ISBN 978-0-486-67870-2 .
3. ↑ Fred Buckley, Frank Harary. Om den euklidiska dimensionen av ett hjul // Grafer och kombinatorik. - 1988. - V. 4 , nr. 1 . — S. 23–30 . - doi : 10.1007/BF01864150 .
4. ↑ Ralph J. Faudree, Brendan D. McKay. En gissning om Erdős och Ramsey-talet r ( W 6 ) // J. Combinatorial Math. och Combinatorial Comput. - 1993. - T. 13 . — S. 23–31 .