Wykres jednorodny
W matematyce graf k - ultrahomogeniczny jest grafem , w którym każdy izomorfizm między dwoma indukowanymi podgrafami o co najwyżej k wierzchołkach można rozszerzyć na automorfizm całego grafu. A k - wykres jednorodny jest zgodny z osłabioną wersją tej samej właściwości, w której każdy izomorfizm między dwoma indukowanymi podgrafami implikuje istnienie automorfizmu całego grafu, który odwzorowuje jeden podgraf na drugi (ale niekoniecznie rozszerza dany izomorfizm).
Graf jednorodny to graf, który jest k -jednorodny dla każdego k lub równoważnie k -ultrajednorodny dla każdego k .
Klasyfikacja
Jedynymi skończonymi grafami jednorodnymi są grafy skupień mK n utworzone z rozłącznych związków izomorficznych pełnych grafów , grafy Turana utworzone jako grafy dopełnienia mK n , graf wieżowy 3 × 3 i 5 - cyklowy .
Jedynymi policzalnie nieskończonymi grafami jednorodnymi są rozłączne sumy izomorficznych pełnych grafów (z rozmiarem każdego pełnego wykresu, liczbą pełnych wykresów lub obiema liczbami policzalnie nieskończonymi), ich grafy dopełnienia, grafy Hensona wraz z ich grafami dopełnienia i wykres Rado .
Jeśli graf jest 5-ultrajednorodny, to jest ultrajednorodny dla każdego k . Istnieją tylko dwa połączone grafy, które są 4-ultrajednorodne, ale nie 5-ultrajednorodne: graf Schläfliego i jego dopełnienie. Dowód opiera się na klasyfikacji skończonych grup prostych .
Wariacje
Graf jest spójny-jednorodny , jeśli każdy izomorfizm między dwoma spójnymi indukowanymi podgrafami można rozszerzyć na automorfizm całego grafu. Oprócz grafów jednorodnych, skończone grafy jednorodne połączone obejmują wszystkie grafy cykli , wszystkie kwadratowe grafy wieży , graf Petersena i 5-regularny graf Clebscha .
Notatki
- Buczak, JMJ (1980), Teoria grup skończonych , dr hab. praca magisterska, Uniwersytet Oksfordzki . Cytowane przez Devillersa (2002) .
- Cameron , Peter Jephson ( 1980 ) _ _ _ Cytowane przez Devillersa (2002) .
- Devillers, Alice (2002), Klasyfikacja niektórych struktur jednorodnych i ultrahomogenicznych , Ph.D. praca magisterska, Université Libre de Bruxelles .
- Gardiner, A. (1976), „Homogeniczne wykresy”, Journal of Combinatorial Theory , Seria B, 20 (1): 94–102, doi : 10.1016/0095-8956 (76) 90072-1 , MR 0419293 .
- Gardiner, A. (1978), „Warunki jednorodności na wykresach”, Journal of Combinatorial Theory , Seria B, 24 (3): 301–310, doi : 10.1016/0095-8956 (78) 90048-5 , MR 0496449 .
- Szary, R.; Macpherson, D. (2010), „Policzalne połączone jednorodne wykresy”, Journal of Combinatorial Theory , Seria B, 100 (2): 97–118, doi : 10.1016/j.jctb.2009.04.002 , MR 2595694 .
- Lachlan, AH; Woodrow, Robert E. (1980), „Policzalne ultrahomogeniczne grafy nieskierowane”, Transactions of the American Mathematical Society , 262 (1): 51–94, doi : 10,2307/1999974 , MR 0583847 .
- Ronse, Christian (1978), „O wykresach jednorodnych”, Journal of the London Mathematical Society , druga seria, 17 (3): 375–379, doi : 10.1112/jlms/s2-17.3.375 , MR 0500619 .