hrabě ze Srikhande | |
---|---|
Pojmenoval podle | S. S. Srikhande |
Vrcholy | 16 |
žebra | 48 |
Poloměr | 2 |
Průměr | 2 |
obvod | 3 |
Automorfismy | 192 |
Chromatické číslo | čtyři |
Chromatický index | 6 |
Vlastnosti |
Silně pravidelné Hamiltonovské symetrické Eulerovo celé číslo |
tloušťka knihy | čtyři |
Počet front | 3 |
Mediální soubory na Wikimedia Commons |
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.
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 .
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] .
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ů .