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 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] It is a special case of a homogenous model.

The proof relies on the classification of finite simple groups.

[4] A graph is connected-homogeneous if every isomorphism between two connected induced subgraphs can be extended to an automorphism of the whole graph.

The top graph is 3-ultrahomogeneous : For any two of its induced subgraphs that are isomorphic and have at most 3 vertices (an example set of subgraphs labeled red and blue), you can choose any mapping of labels from one to the other that keeps the connections between them the same (ex. vertex 2 to 3, 1 to 4, 0 to 5, keeping 2 connected to 1 and 1 connected to 0). You can then replace one with the other (changing the blue vertices to labels 2, 1 and 0), and then relabel the rest of the graph in a way that maintains the connections of the original graph.

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 bottom graph is homogeneous : It is k-homogeneous for any subgraph size k. This also make the graph k-ultrahomogeneous for any subgraph size.