Grafo homogéneo

En matemáticas , un grafo k - ultrahomogéneo es un grafo en el que todo isomorfismo entre dos de sus subgrafos inducidos de a lo sumo k vértices puede extenderse a un automorfismo del grafo completo. Un grafo k - homogéneo cumple una versión debilitada de la misma propiedad, en la que todo isomorfismo entre dos subgrafos inducidos implica la existencia de un automorfismo del grafo completo que mapea un subgrafo al otro (pero no necesariamente extiende el isomorfismo dado). ^{[ 1 ]}

Un grafo homogéneo es un grafo que es k -homogéneo para cada k , o equivalentemente k -ultrahomogéneo para cada k , y por lo tanto, todo grafo homogéneo es también ultrahomogéneo. ^{[ 1 ]} Es un caso especial de un modelo homogéneo .

Los únicos grafos homogéneos finitos son los grafos de clúster mK _n formados a partir de las uniones disjuntas de grafos completos isomorfos , los grafos de Turán formados como los grafos complemento de mK _n , el grafo de torres de 3 × 3 y el ciclo de 5. ^{[ 2 ]}

Los únicos grafos homogéneos infinitamente numerables son las uniones disjuntas de grafos completos isomorfos (donde el tamaño de cada grafo completo, el número de grafos completos, o ambos números son infinitamente numerables), sus grafos complemento, los grafos de Henson junto con sus grafos complemento y el grafo de Rado . ^{[ 3 ]}

Si un grafo es 5-ultrahomogéneo, entonces es ultrahomogéneo para todo 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 demostración se basa en la clasificación de grupos simples finitos . ^{[ 4 ]}

Un grafo es conexo-homogéneo si todo isomorfismo entre dos subgrafos inducidos conexos puede extenderse a un automorfismo del grafo completo. Además de los grafos homogéneos, los grafos conexos-homogéneos finitos incluyen todos los grafos de ciclos , todos los grafos de torres cuadradas , el grafo de Petersen y el grafo de Clebsch 5-regular . ^{[ 5 ]}