Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Self-complementary graph
In the mathematical field of graph theory, a self-complementary graph is a graph which is isomorphic to its complement. The simplest non-trivial self-complementary graphs are the 4-vertex path graph and the 5-vertex cycle graph.
Every Paley graph is self-complementary. For example, the 3 × 3 rook's graph (the Paley graph of order nine) is self-complementary, by a symmetry that keeps the center vertex in place but exchanges the roles of the four side midpoints and four corners of the grid. All strongly regular self-complementary graphs with fewer than 37 vertices are Paley graphs; however, there are strongly regular graphs on 37, 41, and 49 vertices that are not Paley graphs.
The Rado graph is an infinite self-complementary graph.
An n-vertex self-complementary graph has exactly half as many edges of the complete graph, i.e., n(n − 1)/4 edges, and (if there is more than one vertex) it must have diameter either 2 or 3. Since n(n − 1) must be divisible by 4, n must be congruent to 0 or 1 modulo 4; for instance, a 6-vertex graph cannot be self-complementary.
The problems of checking whether two self-complementary graphs are isomorphic and of checking whether a given graph is self-complementary are polynomial-time equivalent to the general graph isomorphism problem.
Hub AI
Self-complementary graph AI simulator
(@Self-complementary graph_simulator)
Self-complementary graph
In the mathematical field of graph theory, a self-complementary graph is a graph which is isomorphic to its complement. The simplest non-trivial self-complementary graphs are the 4-vertex path graph and the 5-vertex cycle graph.
Every Paley graph is self-complementary. For example, the 3 × 3 rook's graph (the Paley graph of order nine) is self-complementary, by a symmetry that keeps the center vertex in place but exchanges the roles of the four side midpoints and four corners of the grid. All strongly regular self-complementary graphs with fewer than 37 vertices are Paley graphs; however, there are strongly regular graphs on 37, 41, and 49 vertices that are not Paley graphs.
The Rado graph is an infinite self-complementary graph.
An n-vertex self-complementary graph has exactly half as many edges of the complete graph, i.e., n(n − 1)/4 edges, and (if there is more than one vertex) it must have diameter either 2 or 3. Since n(n − 1) must be divisible by 4, n must be congruent to 0 or 1 modulo 4; for instance, a 6-vertex graph cannot be self-complementary.
The problems of checking whether two self-complementary graphs are isomorphic and of checking whether a given graph is self-complementary are polynomial-time equivalent to the general graph isomorphism problem.