Hrabat z Chan

hrabat z Chan
Tři grafy Chan (vpravo) a přepínací sady , které je generují ze spojnicového grafu L ( K 8 ) (zelené vrcholy vlevo)
Pojmenoval podle	Lee Chien Chan
Vrcholy	28
žebra	168
Poloměr	2
Průměr	2
obvod	3
Automorfismy	96360384
Vlastnosti	silně pravidelné
Mediální soubory na Wikimedia Commons

Grafy Chan jsou sadou tří 12 pravidelných neorientovaných grafů , z nichž každý má 28 vrcholů a 168 hran. Všechny jsou silně pravidelné a mají stejné parametry a spektrum jako spojnicový graf L ( K 8 ) úplného grafu K 8 . Chan grafy jsou pojmenovány po Li-Chien Chan, který dokázal, že s výjimkou těchto tří grafů je každý spojnicový graf kompletního grafu jednoznačně určen svými silně regulárními parametry grafu [1] .

Vztah s grafy $L(K_{8})$

Každý z těchto tří grafů lze získat přepnutím grafu z . To znamená, že je vybrána podmnožina S vrcholů v grafu , každá hrana, která spojuje vrchol z S s vrcholem, který není v grafu S , je odstraněna a hrany jsou přidány pro každou dvojici vrcholů (opět jeden patří S a druhý nemá), které dříve nebyly spojeny hranou . Mezi grafy, které lze tímto způsobem vytvořit, patří grafy Chan. $L(K_{8})$ $L(K_{8})$ $L(K_{8})$

Viz také

Shrikhandeho graf , podobná výjimka z jedinečnosti parametrů silně regulárních grafů $L(K_{n},n)$

Poznámky

↑ Chang, 1959 , str. 604–613.

Literatura

Chang Li Chien. Jedinečnost a nejedinečnost trojúhelníkových asociačních schémat // Science Record (Peking). - 1959. - T. 3 .

Odkazy

Weisstein, Eric W. "Chang Graphs." Z MathWorld – webový zdroj Wolfram. http://mathworld.wolfram.com/ChangGraphs.html Archivováno 28. ledna 2019 na Wayback Machine
Stránka Andriese E. Brouwera na grafech Chang Archivováno 11. dubna 2018 na Wayback Machine
Nadia Hamoud , „The Chang graphs“ Archivováno 29. srpna 2017 na Wayback Machine