Homogén gráf
A matematika, azon belül a gráfelmélet területén egy k-ultrahomogén gráf olyan gráf, melynek bármely két, legfeljebb k csúcsból álló feszített részgráfja közötti összes izomorfizmus kiterjeszthető a teljes gráf automorfizmusára. Egy k-homogén gráf egy gyengébb változata ennek a tulajdonságnak, melyben két feszített részgráf közötti minden izomorfizmusból következik egy olyan, a teljes gráfra vonatkozó automorfizmus létezése, ami egy részgráfot a másikra visz át (de nem feltétlenül terjeszti ki az adott izomorfizmust).[1]
Egy homogén gráf olyan gráf, ami minden k értékre k-homogén, vagy ami ezzel ekvivalens, minden k értékre k-ultrahomogén.[1]
Osztályozás
[szerkesztés]A véges homogén gráfok közé a következők tartoznak: az izomorf teljes gráfok uniójából álló mKn klasztergráfok, az mKn komplementereiből álló Turán-gráfok, a 3 × 3-as bástyagráf és az 5-kör.[2]
A megszámlálhatóan végtelen homogén gráfok közé a következők tartoznak: izomorf teljes gráfok diszjunkt uniói (ahol az egyes teljes gráfok mérete, a teljes gráfok száma, vagy akár mind a kettő megszámlálhatóan végtelen), ezek komplementerei, a Rado-gráf és a Henson-gráfok.[3]
Ha egy gráf 5-ultrahomogén, akkor minden k-ra ultrahomogén. Csak két olyan összefüggő gráf létezik, ami 4-ultrahomogén, de nem 5-ultrahomogén: ezek a Schläfli-gráf és komplementere. A bizonyítás a véges egyszerű csoportok osztályozásán alapszik.[4]
Változatok
[szerkesztés]Egy gráf akkor összefüggő-homogén (connected-homogeneous), ha bármely két összefüggő feszített részgráfja közötti izomorfizmus kiterjeszthető a teljes gráf automorfizmusára. Az összefüggő-homogén gráfok közé a homogén gráfokon kívül a következők tartoznak: az összes körgráf, az összes négyzetes bástyagráf, a Petersen-gráf és az 5-reguláris Clebsch-gráf.[5]
Fordítás
[szerkesztés]- Ez a szócikk részben vagy egészben a Homogeneous graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek
[szerkesztés]- Buczak, J. M. J. (1980), Finite Group Theory, Ph.D. thesis, Oxford University. As cited by (Devillers 2002).
- Cameron, Peter Jephson (1980), "6-transitive graphs", Journal of Combinatorial Theory, Series B 28: 168–179, DOI 10.1016/0095-8956(80)90063-5. As cited by (Devillers 2002).
- Devillers, Alice (2002), Classification of some homogeneous and ultrahomogeneous structures, Ph.D. thesis, Université Libre de Bruxelles.
- Gardiner, A. (1976), "Homogeneous graphs", Journal of Combinatorial Theory, Series B 20 (1): 94–102, DOI 10.1016/0095-8956(76)90072-1.
- Gardiner, A. (1978), "Homogeneity conditions in graphs", Journal of Combinatorial Theory, Series B 24 (3): 301–310, DOI 10.1016/0095-8956(78)90048-5.
- Gray, R. & Macpherson, D. (2010), "Countable connected-homogeneous graphs", Journal of Combinatorial Theory, Series B 100 (2): 97–118, DOI 10.1016/j.jctb.2009.04.002.
- Lachlan, A. H. & Woodrow, Robert E. (1980), "Countable ultrahomogeneous undirected graphs", Transactions of the American Mathematical Society 262 (1): 51–94, DOI 10.2307/1999974.
- Ronse, Christian (1978), "On homogeneous graphs", Journal of the London Mathematical Society, Second Series 17 (3): 375–379, DOI 10.1112/jlms/s2-17.3.375.
