In mathematics, a k-ultrahomogeneous graph is one where every isomorphism between its induced subgraphs of at most k vertices extends to an automorphism of the entire graph. A k-homogeneous graph satisfies a weaker condition, requiring only that an isomorphism between two induced subgraphs implies the existence of some automorphism mapping one subgraph to the other. A homogeneous graph is k-homogeneous for all k, making it also ultrahomogeneous, and is a special case of a homogenous model.
Classification
The only finite homogeneous graphs are the cluster graphs mKn formed from the disjoint unions of isomorphic complete graphs, the Turán graphs formed as the complement graphs of mKn, the 3 × 3 rook's graph, and the 5-cycle.3
The only countably infinite homogeneous graphs are the disjoint unions of isomorphic complete graphs (with the size of each complete graph, the number of complete graphs, or both numbers countably infinite), their complement graphs, the Henson graphs together with their complement graphs, and the Rado graph.4
If a graph is 5-ultrahomogeneous, then it is ultrahomogeneous for every k. 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.5
Variations
A graph is connected-homogeneous if every isomorphism between two connected induced subgraphs can be extended to an automorphism of the whole graph. In addition to the homogeneous graphs, the finite connected connected-homogeneous graphs include all cycle graphs, all square rook's graphs, the Petersen graph, and the 5-regular Clebsch graph.6
Notes
- 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.
- Gardiner, A. (1976), "Homogeneous graphs", Journal of Combinatorial Theory, Series B, 20 (1): 94–102, doi:10.1016/0095-8956(76)90072-1, MR 0419293.
- Gardiner, A. (1978), "Homogeneity conditions in graphs", Journal of Combinatorial Theory, Series B, 24 (3): 301–310, doi:10.1016/0095-8956(78)90048-5, MR 0496449.
- Gray, R.; Macpherson, D. (2010), "Countable connected-homogeneous graphs", Journal of Combinatorial Theory, Series B, 100 (2): 97–118, doi:10.1016/j.jctb.2009.04.002, MR 2595694.
- Lachlan, A. H.; Woodrow, Robert E. (1980), "Countable ultrahomogeneous undirected graphs", Transactions of the American Mathematical Society, 262 (1): 51–94, doi:10.2307/1999974, MR 0583847.
- Ronse, Christian (1978), "On homogeneous graphs", Journal of the London Mathematical Society, Second Series, 17 (3): 375–379, doi:10.1112/jlms/s2-17.3.375, MR 0500619.
References
Ronse (1978). - Ronse, Christian (1978), "On homogeneous graphs", Journal of the London Mathematical Society, Second Series, 17 (3): 375–379, doi:10.1112/jlms/s2-17.3.375, MR 0500619 https://doi.org/10.1112%2Fjlms%2Fs2-17.3.375 ↩
Ronse (1978). - Ronse, Christian (1978), "On homogeneous graphs", Journal of the London Mathematical Society, Second Series, 17 (3): 375–379, doi:10.1112/jlms/s2-17.3.375, MR 0500619 https://doi.org/10.1112%2Fjlms%2Fs2-17.3.375 ↩
Gardiner (1976). - Gardiner, A. (1976), "Homogeneous graphs", Journal of Combinatorial Theory, Series B, 20 (1): 94–102, doi:10.1016/0095-8956(76)90072-1, MR 0419293 https://doi.org/10.1016%2F0095-8956%2876%2990072-1 ↩
Lachlan & Woodrow (1980). - Lachlan, A. H.; Woodrow, Robert E. (1980), "Countable ultrahomogeneous undirected graphs", Transactions of the American Mathematical Society, 262 (1): 51–94, doi:10.2307/1999974, MR 0583847 https://doi.org/10.2307%2F1999974 ↩
Buczak (1980); Cameron (1980); Devillers (2002). - Buczak, J. M. J. (1980), Finite Group Theory, Ph.D. thesis, Oxford University ↩
Gardiner (1978); Gray & Macpherson (2010) - Gardiner, A. (1978), "Homogeneity conditions in graphs", Journal of Combinatorial Theory, Series B, 24 (3): 301–310, doi:10.1016/0095-8956(78)90048-5, MR 0496449 https://doi.org/10.1016%2F0095-8956%2878%2990048-5 ↩