1980/11/01 by A. H. Lachlan, Robert Woodrow · 1 citation
Mathematics · Computer Science · #Advanced Topology and Set Theory #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Combinatorics #Mathematics #Undirected graph #Countable set #Omega #Graph #Automorphism #Discrete mathematics #Physics
paper · pdf · doi:10.2307/1999974
openalex publication_date 1980/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
Let G = ⟨ VG, EG ⟩ be an undirected graph. The complementary graph G is ⟨ VG, E G ⟩ where (V1, V2) ∈ E G iff V1 ≠ V2 and (V1, V2) ∉ EG. Let K(n) be the complete undirected graph on n vertices and let E be the graph [ill] i.e. ⟨ \ a, b, c\ , \ (b, c), (c, b)\ ⟩. G is ultrahomogeneous just in case every isomorphism of subgraph of smaller cardinality can be lifted to an automorphism of G. Let \mathcal D = \ K(n): n ∈ ω \ ∪ \ E, E\ ∪ \ K(n): n ∈ ω \. Theorem: Let G1, G2 be two countable (infinite) ultrahomogeneous graphs such that for each H ∈ \mathcal D H can be embedded in G1, just in case it can be embedded in G2. Then G1 ≅ G2. Corollary: There are a countable number of countable ultrahomogeneous (undirected) graphs.