Homogén gráf

A Wikipédiából, a szabad enciklopédiából

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]