Hrabě ze Srikhande

Hrabě ze Shrikhande  je hrabě nalezený S. S. Shrikhandem ( anglicky ) v roce 1959 [1] [2] . Graf je silně pravidelný , má 16 vrcholů a 48 hran a každý vrchol má stupeň 6. Každá dvojice uzlů má přesně dva společné sousedy, ať už je pár spojen hranou nebo ne.

Budova

Shrikhandeův graf lze sestavit jako Cayleyův graf, ve kterém je množina vrcholů , a dva vrcholy jsou spojeny právě tehdy, když je rozdíl v .

Vlastnosti

Ve Shrikhandově grafu mají libovolné dva vrcholy I a J dva různé společné sousedy (kromě samotných vrcholů I a J ), což platí bez ohledu na to, zda I a J sousedí nebo ne. Jinými slovy, graf je silně regulární a jeho parametry jsou: {16,6,2,2}, tj . Z této rovnosti vyplývá, že graf je spojen se symetrickými vyváženými neúplnými návrhy bloků ( angl. Balanced Incomplete Block Designs , BIBD). Shrikhandeho graf sdílí tyto parametry přesně s jedním dalším grafem, 4×4 věžovým grafem , to je spojnicový graf L ( K 4,4 ) úplného bipartitního grafu K 4,4 . Poslední graf je jediný spojnicový graf L ( K n, n ), pro který parametry silné pravidelnosti tento graf jednoznačně nedefinují a graf je sdílí s dalším grafem, a to se Shrikhandeho grafem (který není věžovým grafem) [ 2] [3] .  

Graf Srikhande je místně šestiúhelníkový . To znamená, že sousedé každého vrcholu tvoří cyklus šesti vrcholů. Jako každý lokálně cyklický graf je i Shrikhandův graf kostrou Whitneyho triangulace nějakého povrchu. V případě Shrikhandeho grafu je tímto povrchem torus , ve kterém je každý vrchol obklopen šesti trojúhelníky [4] Shrikhandův graf je tedy toroidální graf . Vložení tvoří pravidelné mapování do torusu s 32 trojúhelníkovými plochami. Kostra duálního grafu tohoto zobrazení (vloženého do torusu) je Dyckův graf , kubický symetrický graf.

Shrikhandeho graf není tranzitivní na vzdálenost . Toto je nejmenší vzdálenostně-regulární graf , který není vzdálenostně tranzitivní [5] .

Skupina automorfismu Shrikhandeho grafu má řád 192. Působí tranzitivně na vrcholy, hrany a oblouky grafu. Proto je Shrikhandeho graf symetrickým grafem .

Charakteristický polynom Shrikhandeho grafu je . Shrikhandeho graf je tedy celý graf  – jeho spektrum se skládá výhradně z celých čísel.

Graf má tloušťku knihy 4 a počet front 3 [6] .

Galerie

• Srikhandeho graf je toroidní .

• Barevné číslo hraběte Srikhandeho je 4.

• Chromatický index hraběte Shrikhandeho je 6.

• Hrabě ze Srikhande, nakreslený symetricky.

• hrabě Srikhande z Hamiltonů .

Poznámky

1. ↑ Weisstein, Eric W. Shrikhande Graph  na webu Wolfram MathWorld .
2. ↑ 1 2 Shrikhande, 1959 , str. 781–798.
3. ↑ Harary, 1972 , str. 79.
4. ↑ Brouwer AE Shrikhande graph Archivováno 9. března 2014 na Wayback Machine .
5. ↑ Brouwer, Cohen, Neumaier 1989 , s. 104–105, 136.
6. ↑ Volz, 2018 .

Literatura

• Shrikhande SS Jedinečnost asociačního schématu L 2  // Annals of Mathematical Statistics. - 1959. - T. 30 . — S. 781–798 . - doi : 10.1214/aoms/1177706207 . — .
• Frank Harary. teorie grafů . — Massachusetts: Addison-Wesley, 1972.
  • Harari F. Teorie grafů. - M .: "Mir", 1973.
• , ISBN 0-521-43594-3 
• Brouwer AE, Cohen AM, Neumaier A. Distance-Regular Graphs. - New York: Springer-Verlag, 1989. - S. 104-105, 136.
• Jessica Walzová. Inženýrské lineární rozvržení se SAT. - Univerzita v Tübingenu, 2018. - (Magisterská práce).

Odkazy

• The Shrikhande Graph Archived 24. listopadu 2010 na Wayback Machine , Peter Cameron, srpen 2010.