Self-complementary graph

Self-complementary graph

A self-complementary graph is a graph which is isomorphic to its complement. The simplest self-complementary graphs are the 4-vertex path graph and the 5-vertex cycle graph.

Self-complementary graphs are interesting in their relation to the graph isomorphism problem: 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. [Colbourn M.J., Colbourn Ch.J. "Graph isomorphism and self-complementary graphs", "SIGACT News", 1978, vol. 10, no. 1, 25-29]

An "n"-vertex self-complementary graph has exactly half number of 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. [Sachs, H. (1962) "Über selbstkomplementäre Graphen." "Publ. Math. Debrecen" vol. 9, 270-288] Since "n"("n" −1) must be divisible by 4, "n" must be congruent to 0 or 1 mod 4; for instance, a 6-vertex graph cannot be self-complementary.

Every Paley graph is self-complementary.

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Circulant graph — The Paley graph of order 13, an example of a circulant graph. Crown graphs …   Wikipedia

  • Complement graph — The Petersen graph (on the left) and its complement graph (on the right). In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G …   Wikipedia

  • Self-organization — is a process of attraction and repulsion in which the internal organization of a system, normally an open system, increases in complexity without being guided or managed by an outside source. Self organizing systems typically (though not always)… …   Wikipedia

  • Paley graph — infobox graph name = Paley graph image caption = The Paley graph of order 13 namesake = Raymond Paley vertices = edges = chromatic number = chromatic index = properties = Strongly regularIn mathematics, and specifically graph theory, Paley graphs …   Wikipedia

  • Rado graph — The Rado graph, as numbered by Rado (1964). In the mathematical field of graph theory, the Rado graph, also known as the random graph or the Erdős–Renyi graph, is the unique (up to isomorphism) countable graph R such that for any finite graph G… …   Wikipedia

  • Skew-symmetric graph — In graph theory, a branch of mathematics, a skew symmetric graph is a directed graph that is isomorphic to its own transpose graph, the graph formed by reversing all of its edges. The isomorphism is required to be an involution without any fixed… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Grafo autocomplementario — El estilo de esta traducción aún no ha sido revisado por terceros. Si eres hispanohablante nativo y no has participado en esta traducción puedes colaborar revisando y adaptando el estilo de ésta u otras traducciones ya acabadas …   Wikipedia Español

  • Long-tail traffic — This article covers a range of tools from different disciplines that may be used in the important science of determining the probability of rare events. The terms long range dependent , self similar and heavy tailed are very close in meaning.… …   Wikipedia

  • Duality (mathematics) — In mathematics, a duality, generally speaking, translates concepts, theorems or mathematical structures into other concepts, theorems or structures, in a one to one fashion, often (but not always) by means of an involution operation: if the dual… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”