Grev Brouwer-Hemers

Brouwer-Hemers grafen er en 20 - regulær urettet graf med 81 hjørner og 810 kanter. Det er en stærkt regelmæssig , afstandstransitiv og Ramanujan-graf . Selvom dens konstruktion er matematisk folklore, blev den opkaldt efter Andreas Brauer og Willem H. Hemers, som beviste sin unikke karakter som en stærkt regulær graf.

Konstruktion

Brouwer-Hemers grafen har flere relaterede algebraiske konstruktioner. En af de enkleste konstruktioner er som en generaliseret Paley-graf af orden 4. Den kan defineres ved at vælge hvert toppunkt fra et endeligt felt , og hvert andet element, der adskiller sig med den fjerde grad, tages som kanter [1] [2] .

Egenskaber

Brouwer-Hemers grafen er den eneste stærkt regulære graf med parametre (81, 20, 1, 6). Det betyder, at den har 81 hjørner, 20 kanter pr. vertex, 1 trekant pr. kant, og en sti, der forbinder hver anden ikke-tilstødende knudepunkt, har længden 6 [3] . Som en meget regulær graf med tredje parameter 1 har Brouwer-Hemers grafen den egenskab, at enhver kant hører til en enkelt trekant. Det vil sige, at det er lokalt lineært . Søgningen efter store tætte grafer med denne egenskab er en af ​​formuleringerne af Rouzi-Szemeredi-problemet [4] .

Da grafen er strengt regulær, er den afstandstransitiv [5] .

Historie

Selvom Brouwer skrev, at konstruktionen af ​​denne graf er "folklore" og citerede en tidlig artikel fra 1964 om latinske kvadrater af Dale M. Mesner [1] , er grafen opkaldt efter Andreas Brouwer og Willem H. Hemers, som i 1992 offentliggjorde et bevis at det er den eneste strengt regulære graf med sådanne parametre [3] .

Relaterede grafer

Brouwer-Hemers-grafen er den første i en uendelig familie af Ramanujan-grafer defineret som en generalisering af Paley-grafer over et felt med karakteristisk tre [2] . Sammen med tårngrafen og spilgrafen er den en af ​​tre mulige stærkt regulære grafer, hvis parametre er af formen [6] .

Grafen skal skelnes fra Sudoku-grafen , en anden 20-regulær graf med 81 hjørner. En Sudoku-graf fås fra et Sudoku -puslespil ved at placere et toppunkt i hver Sudoku-celle og forbinde kanter med de hjørner, der er i samme række, kolonne eller blok i puslespillet. Grafen har mange kliker med 9 hjørner og kræver 9 farver for enhver farve . Denne grafs 9-farvefarvning beskriver løsningen til et Sudoku-puslespil [7] [8] . Som en kontrast, i Brouwer-Hemers grafen, er de største kliker trekanter og kun 7 farver er nødvendige for at farvelægge [5] .

Referencer

1. ↑ 1 2 Andries Brouwer. Brouwer-Haemers graf .
2. ↑ 1 2 Ricardo A. Podestá. Spektrene af generaliserede Paley-grafer og applikationer. - 2018. - arXiv : 1812.03332 .
3. ↑ 1 2 Brouwer AE, Haemers WH Struktur og unikhed af den (81,20,1,6) stærkt regulære graf // 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 Ekstreme problemer for lokale egenskaber ved grafer  // The Australasian Journal of Combinatorics. - 1991. - T. 4 . — S. 25–31 .
5. ↑ 1 2 Weisstein, Eric W. Brouwer–Haemers Graph  (engelsk) på Wolfram MathWorld -webstedet .
6. ↑ Andriy V. Bondarenko, Danylo V. Radchenko. På en familie af stærkt regulære grafer med  // Journal of Combinatorial Theory . - 2013. - T. 103 , no. 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 og Gröbner baser: Not only a divertimento // Computer Algebra in Scientific Computing, 9th International Workshop, CASC 2006, Chisinau, Moldova, September 11-15, 2006, Proceedings / Victor G. Ganzha, Ernst W. Mayr, Evgenii V. Vorozhtsov. - Springer, 2006. - T. 4194. - S. 155-165. — (Forelæsningsnotater i datalogi). - doi : 10.1007/11870814_13 .
8. ↑ Agnes M. Herzberg, M. Ram Murty. Sudoku firkanter og kromatiske polynomier  // Notices of the American Mathematical Society . - 2007. - T. 54 , no. 6 . — S. 708–717 .