The middle graph is 3-homogeneous but not 3-ultrahomogeneous: There exists at least one way to map and replace the vertices of one subgraph with the others and then relabel to make an isomorphic graph (1 to 4, 2 to 3, 5 to 0), but not all subgraph-preserving mappings (1 to 0, 2 to 3, 5 to 4) allow the graph to be relabeled to an automorphism of the original.
The right graph is homogeneous: It is k-homogeneous for any subgraph size k. This also make the graph k-ultrahomogeneous for any subgraph size.
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. A k-homogeneous graph obeys a weakened version of the same property in which every isomorphism between two induced subgraphs implies the existence of an automorphism of the whole graph that maps one subgraph to the other (but does not necessarily extend the given isomorphism).[1]
A homogeneous graph is a graph that is k-homogeneous for every k, or equivalently k-ultrahomogeneous for every k, and thus, every homogeneous graph is also ultrahomogeneous.[1] It is a special case of a homogenous model.
Classification
editThe 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.[2]
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.[3]
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.[4]
Variations
editA 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.[5]
Notes
editReferences
edit- 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 (2): 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, JSTORย 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.
