Homogenní graf - Homogeneous graph
v matematika, a k-ultrahomogenní graf je graf ve kterém každý izomorfismus mezi dvěma z nich indukované podgrafy maximálně k vrcholy lze rozšířit na automorfismus celého grafu. A k-homogenní graf poslouchá oslabenou verzi stejné vlastnosti, ve které každý izomorfismus mezi dvěma indukovanými podgrafy implikuje existenci automorfismu celého grafu, který mapuje jeden podgraf na druhý (ale nemusí nutně rozšiřovat daný izomorfismus).[1]
A homogenní graf je graf, který je k-homogenní pro každého knebo ekvivalentně k- vícehomogenní pro každého k.[1]
Klasifikace
Jediné konečné homogenní grafy jsou shlukové grafy mKn vytvořený z disjunktní odbory izomorfní kompletní grafy, Turánovy grafy vytvořen jako doplňkové grafy z mKn, 3 × 3 věžní graf acyklus.[2]
Jediný počítatelně nekonečný homogenní grafy jsou nesouvislé svazky izomorfních úplných grafů (s velikostí každého úplného grafu, počtem úplných grafů nebo oběma čísly počítatelně nekonečnými), jejich doplňkovými grafy, Hensonovy grafy společně s jejich doplňkovými grafy a Rado graf.[3]
Pokud je graf 5-ultrahomogenní, pak je ultrahomogenní pro všechny kJsou jen dva připojeno grafy, které jsou 4-ultrahomogenní, ale ne 5-ultrahomogenní: the Schläfliho graf a jeho doplněk. Důkaz se opírá o klasifikace konečných jednoduchých skupin.[4]
Variace
Graf je připojeno-homogenní pokud lze každý izomorfismus mezi dvěma spojenými indukovanými podgrafy rozšířit na automorfismus celého grafu. Kromě homogenních grafů zahrnují konečné spojené homogenní grafy všechny cyklické grafy, celý čtverec věže grafy, Petersenův graf a 5 pravidelných Clebschův graf.[5]
Poznámky
Reference
- Buczak, J. M. J. (1980), Teorie konečné skupiny, Ph.D. práce, Oxford University. Jak uvádí Devillers (2002).
- Cameron, Peter Jephson (1980), „6-tranzitivní grafy“, Journal of Combinatorial Theory, Řada B, 28: 168–179, doi:10.1016/0095-8956(80)90063-5. Jak uvádí Devillers (2002).
- Devillers, Alice (2002), Klasifikace některých homogenních a ultrahomogenních struktur, Ph.D. práce, Université Libre de Bruxelles.
- Gardiner, A. (1976), "Homogenní grafy", Journal of Combinatorial Theory, Řada B, 20 (1): 94–102, doi:10.1016/0095-8956(76)90072-1, PAN 0419293.
- Gardiner, A. (1978), "Homogenita podmínky v grafech", Journal of Combinatorial Theory, Řada B, 24 (3): 301–310, doi:10.1016/0095-8956(78)90048-5, PAN 0496449.
- Gray, R .; Macpherson, D. (2010), „Countable connected-homogeneous graphs“, Journal of Combinatorial Theory, Řada B, 100 (2): 97–118, doi:10.1016 / j.jctb.2009.04.002, PAN 2595694.
- Lachlan, A. H .; Woodrow, Robert E. (1980), „Countable ultrahomogenene unirected graphs“, Transakce Americké matematické společnosti, 262 (1): 51–94, doi:10.2307/1999974, PAN 0583847.
- Ronse, Christian (1978), „O homogenních grafech“, Journal of the London Mathematical Society, Druhá série, 17 (3): 375–379, doi:10.1112 / jlms / s2-17.3.375, PAN 0500619.