Surf Wiki
Save to docs
general/graph-families

From Surf Wiki (app.surf) — the open knowledge base

Self-complementary graph

Graph which is isomorphic to its complement

Self-complementary graph
Summary

Graph which is isomorphic to its complement

Graph A is isomorphic to its complement.]]

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.

Examples

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.{{citation | doi-access =

The Rado graph is an infinite self-complementary graph.{{citation

Properties

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.{{citation

Computational complexity

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.

References

References

  1. (1978). "Graph isomorphism and self-complementary graphs". [[SIGACT News]].
Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

graph-families
Want to explore this topic further?

Ask Mako anything about Self-complementary graph — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report