Greve Brouwer-Hemers

Brouwer-Hemers-grafen är en 20 - vanlig oriktad graf med 81 hörn och 810 kanter. Det är en starkt regelbunden , distanstransitiv och Ramanujan-graf . Även om dess konstruktion är matematisk folklore, var den uppkallad efter Andreas Brauer och Willem H. Hemers, som bevisade sin unika karaktär som en starkt regelbunden graf.

Byggnad

Brouwer-Hemers-grafen har flera relaterade algebraiska konstruktioner. En av de enklaste konstruktionerna är som en generaliserad Paley-graf av ordning 4. Den kan definieras genom att välja varje vertex från ett ändligt fält , och vartannat element som skiljer sig åt fjärde graden tas som kanter [1] [2] .

Egenskaper

Brouwer-Hemers-grafen är den enda starkt regelbundna grafen med parametrar (81, 20, 1, 6). Detta betyder att den har 81 hörn, 20 kanter per hörn, 1 triangel per kant, och en bana som förbinder varannan icke intilliggande hörn har längden 6 [3] . Som en starkt regelbunden graf med tredje parameter 1 har Brouwer-Hemers graf egenskapen att vilken kant som helst tillhör en enskild triangel. Det vill säga den är lokalt linjär . Sökandet efter stora täta grafer med denna egenskap är en av formuleringarna av Rouzi-Szemeredi-problemet [4] .

Eftersom grafen är strikt regelbunden är den avståndstransitiv [5] .

Historik

Även om Brouwer skrev att konstruktionen av denna graf är "folklore" och citerade en tidning från 1964 om latinska kvadrater av Dale M. Mesner [1] , är grafen uppkallad efter Andreas Brouwer och Willem H. Hemers, som 1992 publicerade ett bevis att det är den enda strikt regelbundna grafen med sådana parametrar [3] .

Relaterade grafer

Brouwer-Hemers-grafen är den första i en oändlig familj av Ramanujan-grafer definierade som en generalisering av Paley-grafer över ett fält med karakteristiska tre [2] . Tillsammans med torngrafen och spelgrafen är den en av tre möjliga starkt regelbundna grafer vars parametrar är av formen [6] .

Grafen måste särskiljas från Sudoku-grafen , en annan 20-regelbunden graf med 81 hörn. En Sudoku-graf erhålls från ett Sudoku- pussel genom att placera en vertex i varje Sudoku-cell och ansluta kanter till de hörn som finns i samma rad, kolumn eller block i pusslet. Grafen har många klicker med 9 hörn och kräver 9 färger för alla färger . Den 9-färgade färgningen av denna graf beskriver lösningen till ett Sudoku-pussel [7] [8] . Som en kontrast, i Brouwer-Hemers-grafen, är de största klickarna trianglar och endast 7 färger behövs för färgläggning [5] .

Referenser

1. ↑ 1 2 Andries Brouwer. Brouwer–Haemers graf .
2. ↑ 1 2 Ricardo A. Podestá. Spektra för generaliserade Paley-grafer och tillämpningar. - 2018. - arXiv : 1812.03332 .
3. ↑ 1 2 Brouwer AE, Haemers WH Struktur och unikhet hos den (81,20,1,6) starkt regelbundna grafen // Diskret matematik. - 1992. - T. 106/107 . — s. 77–82 . - doi : 10.1016/0012-365X(92)90532-K .
4. ↑ Clark LH, Entringer RC, McCanna JE, Székely LA Extrema problem för lokala egenskaper hos grafer  // The Australasian Journal of Combinatorics. - 1991. - T. 4 . — S. 25–31 .
5. ↑ 1 2 Weisstein, Eric W. Brouwer–Haemers Graph  (engelska) på Wolfram MathWorld -webbplatsen .
6. ↑ Andriy V. Bondarenko, Danylo V. Radchenko. På en familj av starkt regelbundna grafer med  // Journal of Combinatorial Theory . - 2013. - T. 103 , nr. 4 . — S. 521–531 . - doi : 10.1016/j.jctb.2013.05.005 .
7. ↑ Jesús Gago-Vargas, Maria Isabel Hartillo-Hermoso, Jorge Martín-Morales, Jose Maria Ucha-Enríquez. Sudokus och Gröbner-baser: Not only a divertimento // Computer Algebra in Scientific Computing, 9th International Workshop, CASC 2006, Chisinau, Moldavien, 11-15 september 2006, Proceedings / Victor G. Ganzha, Ernst W. Mayr, Evgenii V. Vorozhtsov. - Springer, 2006. - T. 4194. - S. 155-165. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/11870814_13 .
8. ↑ Agnes M. Herzberg, M. Ram Murty. Sudoku-rutor och kromatiska polynom  // Notices of the American Mathematical Society . - 2007. - T. 54 , nr. 6 . — S. 708–717 .