Homogeneous graph

In mathematics, a k-ultrahomogeneous graph is a graph in which every isomorphism between two of its induced subgraphs of at most k vertices can be extended to an automorphism of the whole graph.

If a graph is 5-ultrahomogeneous, then it is ultrahomogeneous for every k. The only finite connected graphs of this type are complete graphs, Turán graphs, 3 × 3 rook's graphs, and the 5-cycle.

There are only two connected graphs that are 4-ultrahomogeneous but not 5-ultrahomogeneous: the Schläfli graph and its complement. The proof relies on the classification of finite simple groups.^[1]

The infinite Rado graph is countably ultrahomogeneous.

Notes

^ Buczak (1980); Cameron (1980); Devillers (2002).

References

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.

[1] Buczak (1980); Cameron (1980); Devillers (2002).

[1]