mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, a ''k''-ultrahomogeneous graph is a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

in which every

isomorphism In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...

between two of its

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...

s of at most ''k'' vertices can be extended to an

automorphism In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms ...

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). A homogeneous graph is a graph that is ''k''-homogeneous for every ''k'', or equivalently ''k''-ultrahomogeneous for every ''k''.

Classification

The only finite homogeneous graphs are the

cluster graph In graph theory, a branch of mathematics, a cluster graph is a graph formed from the disjoint union of complete graphs. Equivalently, a graph is a cluster graph if and only if it has no three-vertex induced path; for this reason, the cluster ...

s ''mK''_''n'' formed from the disjoint unions of isomorphic

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...

s, the

Turán graph The Turán graph, denoted by T(n,r), is a complete multipartite graph; it is formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to di ...

s formed as the

complement graph In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of a ...

s of ''mK''_''n'', the 3 × 3

rook's graph In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and each edge connects two squares on the same row (rank) or on ...

, and the 5- cycle. The only

countably infinite In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...

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 graph In graph theory, the Henson graph is an undirected infinite graph, the unique countable homogeneous graph that does not contain an -vertex clique (graph theory), clique but that does contain all -free finite graphs as induced subgraphs. For instanc ...

s together with their complement graphs, and the

Rado graph In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed (with probability one) by choosing independently at random for each pair of its vertices whe ...

. If a graph is 5-ultrahomogeneous, then it is ultrahomogeneous for every ''k''. There are only two

connected Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...

graphs that are 4-ultrahomogeneous but not 5-ultrahomogeneous: the

Schläfli graph In the mathematical field of graph theory, the Schläfli graph, named after Ludwig Schläfli, is a 16- regular undirected graph with 27 vertices and 216 edges. It is a strongly regular graph with parameters srg(27, 16, 10, 8). ...

and its complement. The proof relies on the

classification of finite simple groups In mathematics, the classification of the finite simple groups is a result of group theory stating that every finite simple group is either cyclic, or alternating, or it belongs to a broad infinite class called the groups of Lie type, or else it ...

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-homogeneous graphs include all

cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

s, all square

s, the

Petersen graph In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is n ...

, and the 5-regular

Clebsch graph In the mathematical field of graph theory, the Clebsch graph is either of two complementary graphs on 16 vertices, a 5-regular graph with 40 edges and a 10-regular graph with 80 edges. The 80-edge graph is the dimension-5 halved cube graph; it ...

Notes

References

*. As cited by . *. As cited by . *. *. *. *. *. *. {{refend Graph families