Greve Clebsha

Greve Clebsha
Toppar 16
revben 40
Radie 2
Diameter 2
Omkrets fyra
Automorfismer 1920
Kromatiskt nummer 4 [1]
Egenskaper Starkt regelbunden
Hamiltonsk graf
Triangelfri
graf Cayley-graf
Vertex-transitiv
Kant-transitiv
Avstånd-transitiv
 Mediafiler på Wikimedia Commons

I grafteorin förstås en Clebsch-graf som en av två komplementära grafer med 16 hörn. En av dem har 40 kanter och är en 5- regelbunden graf , den andra har 80 kanter och är en 10-regelbunden graf. 80-kantsvarianten är en halv kubgraf5:e ordningen. Utnämnd till greve av Clebsch 1968 av Seidel [2] på grund av dess samband med konfigurationen av linjer av fjärde ordningens yta, upptäckt 1868 av den tyske matematikern Alfred Clebsch . 40-kantsvarianten är en vikbar kubgraf5:e ordningen. Den är också känd som Greenwood-Gleason-grafen efter Greenwoods och Gleasons arbete [3] , där de använde denna graf för att beräkna Ramsey-talet R (3,3,3) = 17 [3] [4] [5 ] .

Byggnad

Vikbar kubgraf5:e ordningen (5-regelbunden Clebsch-graf) kan konstrueras genom att lägga till kanter mellan motsatta hörn av en 4-dimensionell hyperkubgraf (I en n - dimensionell hyperkub är ett par hörn motsatta om det kortaste avståndet mellan dem innehåller n kanter). Den kan också konstrueras från en 5-dimensionell hyperkubgraf genom att dra ihop varje par av motsatta hörn.

En annan konstruktion som ger samma graf är att skapa en vertex för varje element i det finita fältet GF (16) och koppla två hörn med en kant om skillnaden mellan motsvarande element i fältet är en kub [6] .

Halv kub graf5:e ordningen (10-regelbunden Clebsch-graf) är komplementet till en 5-regelbunden graf. Den kan också byggas från hörn av en 5-dimensionell hyperkub genom att koppla ihop par av hörn mellan vilka Hamming-avståndet är exakt två. Denna konstruktion bildar två delmängder med 16 hörn vardera, inte anslutna till varandra. Båda erhållna graferna är isomorfa till den 10-regelbundna Clebsch-grafen.

Egenskaper

En 5-regelbunden Clebsch-graf är en starkt regelbunden 5-gradsgraf med parametrar [7] [8] . Dess komplement, den 10-regelbundna Clebsch-grafen, är också starkt regelbunden [1] [5] .

Den 5-regelbundna Clebsch-grafen är Hamiltonsk , icke- planär och icke-Eulerisk . Båda graferna är 5 -vertex-anslutna och 5 -kant-anslutna . En subgraf som genereras av tio hörn som inte är grannar till någon vertex i denna graf är isomorf till Petersen-grafen .

Kanterna på den kompletta grafen K 16 kan delas upp i tre frånkopplade kopior av den 5-vanliga Clebsch-grafen. Eftersom Clebsch-grafen inte innehåller trianglar visar detta att det finns en trefärgad färgning utan trianglar på grafens kanter K 16 . Således kan Ramsey-talet R (3,3,3), som beskriver det minsta antalet hörn i en komplett graf under trefärgad färgning utan trianglar, vara mindre än 17. Greenwood och Gleason använde denna konstruktion som en del av sitt bevis på likhet R (3,3, 3) = 17 [3] [9] .

Den 5-regelbundna Clebsch- grafen är en Keller-graf av dimension två och tillhör en familj av grafer som används för att hitta täckningen av högdimensionella euklidiska utrymmen av hyperkuber som inte har gemensamma ytor.

Algebraiska egenskaper

Det karakteristiska polynomet för en 5-regelbunden Clebsch-graf är . Således är Clebsch-grafen en heltalsgraf - dess spektrum består helt av heltal [5] . Clebsch-grafen är den enda grafen med ett sådant karakteristiskt polynom.

Den 5-regelbundna Clebsch- grafen är en Cayley-graf med en ordning 1920 automorfismgrupp isomorf till Coxeter-gruppen . Som i vilken Cayley-graf som helst, verkar automorfismgruppen transitivt på sina hörn, vilket gör den vertextransitiv . I själva verket är det en symmetrisk graf , och därför är den kanttransitiv och distanstransitiv .

Galleri

Anteckningar

  1. ↑ 1 2 . Eric W. Weisstein. Clebsch-graf. . Från MathWorld - En Wolfram webbresurs. Hämtad 13 augusti 2009. Arkiverad från originalet 7 februari 2009.
  2. ↑ JJ Seidel, Starkt regelbundna grafer med (−1,1,0) närliggande matris med egenvärde 3, Lin. Alg. Appl. 1 (1968) 281-298.
  3. ↑ 1 2 3 R. E. Greenwood, Andrew Gleason. Kombinatoriska relationer och kromatiska grafer  // Canadian Journal of Mathematics. - 1955. - T. 7 . - S. 1-7 . - doi : 10.4153/CJM-1955-001-4 .
  4. ↑ A. Clebsch. Ueber die Flächen vierter Ordnung, welche eine Doppelcurve zweiten Grades besitzen // J. fur Math. - 1868. - T. 69 . - S. 142-184 .
  5. ↑ 1 2 3 The Clebsch Graph på Bill Cherowitzos hemsida . Hämtad 25 oktober 2013. Arkiverad från originalet 29 oktober 2013.
  6. ↑ De Clerck, Frank Konstruktioner och karakteriseringar av (halv)partiella geometrier . Summer School on Finite Geometries 6 (1997). Hämtad 25 oktober 2013. Arkiverad från originalet 15 juni 2011.
  7. ↑ Problem i algebraisk kombinatorik // Electronic Journal of Combinatorics . - 1995. - T. 2 . - S. 3 .
  8. ↑ Peter J. Cameron Starkt regelbundna grafer Arkiverade 29 oktober 2013 på Wayback Machine på DesignTheory.org, 2001
  9. ↑ Hugo S. Sun, M.E. Cohen. Ett enkelt bevis på Greenwood–Gleason-utvärderingen av Ramsey-numret R (3,3,3) // The Fibonacci Quarterly. - 1984. - T. 22 , nr. 3 . - S. 235-238 .