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).
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.
Osztályozá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.
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.
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.; ; .
Változatok 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.;
Fordítás
Jegyzetek
. As cited by . . As cited by . . . . . . .
Kategória:Gráfcsaládok