Self-complementary graph
A self-complementary graph is a simple undirected graph that is isomorphic to its complement, meaning there exists a bijection between the vertices that maps edges to non-edges and vice versa.[1] Such graphs necessarily have an order n (number of vertices) satisfying n ≡ 0 or 1 (mod 4), with exactly n(n-1)/4 edges, ensuring the edge count matches that of the complement.[2] The concept of self-complementary graphs was introduced independently by Horst Sachs in 1962 and Gerhard Ringel in 1963, with early enumerative work by Ronald Read shortly thereafter.[1] These graphs possess notable structural properties, including connectivity, a diameter of 2 or 3, and the presence of Hamiltonian paths; for n > 5, they contain cycles of every length from 3 to n-2.[2] Their degree sequences are symmetric around (n-1)/2, reflecting the inherent symmetry with their complements.[1] Prominent examples include the path graph P4 on 4 vertices and the cycle graph C5 on 5 vertices, both of which are self-complementary.[2] More advanced constructions, such as Paley graphs of prime order p ≡ 1 (mod 4), yield regular self-complementary graphs that are also strongly regular.[1] The enumeration of self-complementary graphs on n vertices forms the sequence 1, 0, 0, 1, 2, 0, 0, 10, 36, ... (OEIS A000171), with exact counts known up to relatively large n through computational catalogs.[2] Self-complementary graphs are significant in graph theory due to their connections to isomorphism testing—recognizing them is polynomially equivalent to the graph isomorphism problem—and applications in reconstructing graphs from edge sets or studying symmetric structures like antimorphisms.[1] Ongoing research explores generalizations, such as almost self-complementary graphs and multipartite variants, highlighting their role in extremal graph theory and combinatorial design.[1]Fundamentals
Definition
A self-complementary graph is defined in the context of undirected simple graphs without loops or multiple edges. The complement \overline{G} of a graph G with vertex set V(G) is the graph on the same vertex set where two distinct vertices are adjacent in \overline{G} if and only if they are not adjacent in G.[3] This complement consists of all possible edges absent from G, forming the complete graph K_n minus the edges of G, where n = |V(G)|.[3] A graph G on n vertices is self-complementary if it is isomorphic to its complement \overline{[G](/page/G)}.[3] Graph isomorphism here means there exists a bijection \phi: V(G) \to V(\overline{G}) such that for any distinct vertices u, v \in V(G), the pair uv is an edge in G if and only if \phi(u)\phi(v) is an edge in \overline{G}.[3] This bijection, often termed an antimorphism, preserves the adjacency structure while mapping edges in G to non-edges in \overline{G} and vice versa.[3] Since G and \overline{G} are isomorphic, they must have the same number of edges, implying that |E(G)| = |\overline{G}|. The total possible edges on n vertices is \binom{n}{2} = n(n-1)/2, so each has exactly half, or |E(G)| = n(n-1)/4.[3] For this to be an integer, n(n-1) must be divisible by 4.[3]History
The study of self-complementary graphs originated in the early 1960s with foundational contributions from H. Sachs, who introduced the concept in the context of antimorphisms and graph symmetries in his 1962 paper.[3] Sachs developed construction methods using antimorphisms, proving that every antimorphism corresponds to one in some regular or almost regular self-complementary graph, and demonstrated the existence of circulant self-complementary graphs for orders n whose prime divisors are congruent to 1 modulo 4. Independently, G. Ringel explored similar ideas in 1963, focusing on structural properties and self-complementary structures, including properties and construction techniques via antimorphisms that paralleled Sachs' discoveries.[4] That same year, R. C. Read advanced the field through work on enumeration, providing formulas for the number of self-complementary graphs and digraphs on even and odd orders, and proposed counting methods based on antimorphisms while reviewing prior results.[3] In the 1970s, research shifted toward structural theorems and Hamiltonicity, with R. A. Gibbs investigating eigenvalues of self-complementary graphs and charting key developments in the area. S. B. Rao made significant strides on Hamiltonicity, establishing in 1977 that self-complementary graphs on more than 5 vertices contain circuits of lengths 3 through n-2, and providing characterizations of non-Hamiltonian self-complementary graphs; his 1979 paper offered a comprehensive solution to the Hamiltonian problem for these graphs, showing that non-Hamiltonian examples are highly constrained except for specific cases on orders $4k. C. R. J. Clapham contributed to path properties, proving in 1974 that every finite self-complementary graph contains a Hamiltonian path (or arc), and in 1975 exploring Hamiltonian arcs in infinite self-complementary graphs. These works built a robust framework for understanding connectivity and cycle structures. In 1973, Clapham also studied the number of triangles in self-complementary graphs.[3] The 1980s saw further exploration of paths and related properties, with Clapham extending analyses of Hamiltonian paths and P. Camion addressing traceable aspects in self-complementary graphs around 1975, influencing later path-focused studies. Contributions from J. Akiyama and F. Harary on connectivity, as well as C. Y. Chao and E. G. Whitehead on chromatic numbers, highlighted structural intricacies. By the 1990s, A. R. Farrugia's 1999 master's thesis and accompanying survey synthesized the field, compiling over 200 papers on topics from distance and connectivity to enumerations, serving as a key reference that underscored the maturity of the area.[3] Subsequent developments evolved self-complementary graphs into broader generalizations, such as almost self-complementary graphs, which are isomorphic to graphs differing by a single edge from their complement, extending classical constructions and properties. Applications emerged in coding theory, where self-complementary structures inform circular codes and error-correcting mechanisms, as explored in analyses of code graphs and their path properties.[5][3] In the 2020s, ongoing research has included new constructions of regular and quasi-regular self-complementary graphs, enumerations of self-complementary circulant graphs on prime-power orders, and studies of flip graphs on self-complementary ideals in chain product posets.[6][7][8]Properties
Basic Properties
A self-complementary graph on n vertices exists only if n \equiv 0 or $1 \pmod{4}. This condition arises because the total number of possible edges in the complete graph K_n is \frac{n(n-1)}{2}, and for the graph to be isomorphic to its complement, it must contain exactly half of these edges, so \frac{n(n-1)}{4} must be an integer.[3] Consequently, every self-complementary graph has precisely \frac{n(n-1)}{4} edges. The degree sequence of such a graph is symmetric around \frac{n-1}{2}, meaning that if d_i is the degree of a vertex, then there is a corresponding vertex of degree n-1-d_i. When n = 4k+1 for some integer k \geq 0, the graph is regular of degree \frac{n-1}{2} = 2k.[3] All self-complementary graphs on n > 1 vertices are connected. Additionally, the radius of every self-complementary graph on n > 1 vertices is 2, reflecting the balanced structure imposed by isomorphism to the complement.[3]Advanced Properties
Self-complementary graphs exhibit several advanced structural properties that arise from their isomorphism to their complements. For graphs of order n > 1, the diameter is either 2 or 3, ensuring that any two vertices are connected by a short path, with the complement preserving this bounded distance.[9] Every self-complementary graph contains a Hamiltonian path, a result established by analyzing the degree sequences and applying closure conditions from Dirac's theorem variants. Many such graphs are also Hamiltonian, meaning they possess a Hamiltonian cycle; however, the non-Hamiltonian ones are characterized as "highly constricted," where the graph and its complement both have vertices of degree at most 1 or specific structural bottlenecks, except for a particular exceptional graph on $4k vertices.[10] Regarding cycle structures, every self-complementary graph of order n > 5 contains cycles of every length \ell where $3 \leq \ell \leq n-2, reflecting the balanced edge distribution between the graph and its complement. Furthermore, those that are Hamiltonian are pancyclic, admitting cycles of all lengths from 3 to n.[11] An antimorphism, defined as an isomorphism \phi: [G](/page/G) \to \overline{[G](/page/G)}, viewed as a permutation of the vertices, decomposes into disjoint cycles whose lengths are multiples of 4, except possibly for a single fixed point when n \equiv 1 \pmod{4}; this cycle structure enforces the self-complementarity.[3] The automorphism group \mathrm{Aut}(G) of a self-complementary graph G is isomorphic to \mathrm{Aut}(\overline{G}) due to the isomorphism between G and \overline{G}, but the precise relationship involves an extension by a complementing involution, and no complete characterization of such groups exists beyond specific constructions.[3]Examples
Small Examples
The trivial self-complementary graph is the complete graph K_1 on a single vertex, which has no edges and is isomorphic to its empty complement.[3] On four vertices, there is a unique self-complementary graph up to isomorphism: the path graph P_4. This graph has vertices labeled 1 through 4 and edges connecting 1-2, 2-3, and 3-4; its complement consists of edges 1-3, 1-4, and 2-4, which is isomorphic to P_4 under the vertex permutation that reverses the order of the vertices.[3][12] On five vertices, there are two non-isomorphic self-complementary graphs. One is the cycle graph C_5, with vertices 1 through 5 and edges 1-2, 2-3, 3-4, 4-5, and 5-1; an isomorphism to its complement can be achieved by mapping each vertex i to i+2 \pmod{5}.[3][13] The other is the bull graph, formed by a triangle on vertices a, b, c (edges a-b, b-c, c-a) with two pendant vertices d adjacent only to b and e adjacent only to c.[13][14] On eight vertices, there are ten non-isomorphic self-complementary graphs, as enumerated through exhaustive generation and isomorphism checking.[15][3] On nine vertices, there are 36 non-isomorphic self-complementary graphs, including four that are regular of degree 4.[3][15]Infinite Families
One prominent infinite family of self-complementary graphs consists of the Paley graphs. For a prime power q \equiv 1 \pmod{4}, the Paley graph of order q has vertex set the elements of the finite field \mathbb{F}_q, with an edge between distinct vertices x and y if and only if x - y is a nonzero quadratic residue in \mathbb{F}_q. These graphs are self-complementary, as the complement corresponds to connecting vertices whose differences are quadratic nonresidues, and multiplication by a fixed quadratic nonresidue induces an isomorphism between the graph and its complement.[16] The Rado graph, also known as the infinite random graph, provides an example in the infinite setting. It is the unique (up to isomorphism) countable graph satisfying the extension property: for any finite disjoint sets U and V of vertices, there exists a vertex adjacent to all vertices in U and none in V. This graph is self-complementary, since the extension property is preserved under complementation, implying an isomorphism between the graph and its complement.[17] Recursive constructions generate further infinite families of finite self-complementary graphs. Starting from a self-complementary graph on n vertices where n \equiv 0 or $1 \pmod{4}, one can form a larger self-complementary graph on n+4 vertices by taking the disjoint union with a path on four vertices P_4 (which is self-complementary) and adding specific edges between the components to preserve the property; alternatively, G-joins of two self-complementary graphs on equal orders can yield another self-complementary graph when the join parameters are chosen appropriately. These methods produce arbitrarily large self-complementary graphs, establishing infinite sequences.[3] Self-complementary graphs that are also strongly regular form another notable family, often arising from combinatorial designs. The Paley graphs themselves are strongly regular with parameters (q, (q-1)/2, (q-5)/4, (q-1)/4), and beyond these, an additional infinite family of self-complementary symmetric (hence vertex-transitive and strongly regular) graphs exists, constructed via certain Paley-type tournaments over finite fields of characteristic not 2. Examples include graphs of orders 5, 9, 13, 17, and 25, which can be realized as conference graphs or quadratic residue graphs on appropriate orders.[18] For orders n \equiv 2 or $3 \pmod{4}, where self-complementary graphs do not exist, almost self-complementary graphs provide analogous infinite families. A graph on n vertices is almost self-complementary if it is isomorphic to the complement minus a perfect matching (when n is even) or a near-perfect matching (when n is odd). Constructions include extensions of smaller almost self-complementary graphs by adding structures like modified paths or using symmetric designs, yielding sequences for all such n; for instance, starting from the almost self-complementary graph on 2 vertices and recursively adjoining components preserves the property.[19]Enumeration
Counts for Small Orders
Self-complementary graphs exist only for vertex orders n \equiv 0 or $1 \pmod{4}. The enumeration of unlabeled self-complementary graphs (up to isomorphism) for small such n has been a focus of early work in graph enumeration, providing exact counts that illustrate the growth in complexity as n increases. The following table lists these counts up to n=21:| n | Number of unlabeled self-complementary graphs |
|---|---|
| 1 | 1 |
| 4 | 1 |
| 5 | 2 |
| 8 | 10 |
| 9 | 36 |
| 12 | 720 |
| 13 | 5600 |
| 16 | 703760 |
| 17 | 11220000 |
| 20 | 9168331776 |
| 21 | 293293716992 |