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. A 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.[1]

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 graphs, 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 Rado graph, and the Henson graphs.[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]

Notes

  1. 1 2 Ronse (1978).
  2. ↑ Gardiner (1976).
  3. ↑ Lachlan & Woodrow (1980).
  4. ↑ Buczak (1980); Cameron (1980); Devillers (2002).

References

This article is issued from Wikipedia - version of the 8/7/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.