En matemáticas , un grafo k - ultrahomogéneo es un grafo en el que todo isomorfismo entre dos de sus subgrafos inducidos de como máximo k vértices puede extenderse a un automorfismo de todo el grafo. Un grafo k - homogéneo obedece a una versión debilitada de la misma propiedad en la que todo isomorfismo entre dos subgrafos inducidos implica la existencia de un automorfismo de todo el grafo que mapea un subgrafo al otro (pero no necesariamente extiende el isomorfismo dado). [1]
Un gráfico homogéneo es un gráfico que es k -homogéneo para cada k , o equivalentemente k -ultrahomogéneo para cada k . [1] Es un caso especial de un modelo homogéneo .
Los únicos grafos homogéneos finitos son los grafos de conglomerados mK n formados a partir de las uniones disjuntas de grafos completos isomorfos , los grafos de Turán formados como los grafos complementarios de mK n , el grafo de torre de 3 × 3 y el 5- ciclo . [2]
Los únicos grafos homogéneos infinitos contables son las uniones disjuntas de grafos completos isomorfos (con el tamaño de cada grafo completo, el número de grafos completos o ambos números contablemente infinitos), sus grafos complementarios, los grafos de Henson junto con sus grafos complementarios y el grafo de Rado . [3]
Si un grafo es 5-ultrahomogéneo, entonces es ultrahomogéneo para cada k . Solo hay dos grafos conexos que son 4-ultrahomogéneos pero no 5-ultrahomogéneos: el grafo de Schläfli y su complemento. La prueba se basa en la clasificación de grupos simples finitos . [4]
Un grafo es homogéneo-conexo si cada isomorfismo entre dos subgrafos inducidos conexos puede extenderse a un automorfismo del grafo completo. Además de los grafos homogéneos, los grafos homogéneos-conexos finitos incluyen todos los grafos de ciclos , todos los grafos de torre cuadrados , el grafo de Petersen y el grafo de Clebsch 5-regular . [5]