Self-complementary graphs and Ramsey numbers part I: The decomposition and construction of self-complementary graphs

Abstract

A new method of studying self-complementary graphs, called the decomposition method, is proposed in this paper. Let G be a simple graph. The complement of G, denoted by Ḡ, is the graph in which V(Ḡ) = V(G); and for each pair of vertices u,v in Ḡ, uv ∈ G-E(Ḡ) if and only if uv ∉ E(G). G is called a self-complementary graph if G and Ḡ are isomorphic. Let G be a self-complementary graph with the vertex set V(G)={v1v2,...,v4n}, where dG(v1)≤dG(v2)≤⋯ ≤dG(v4n). Let H = G[v1v2,...,v2n], H′ = G[v2n+1, V2n+2,...,v4n] and H* = G - E(H) - E(H′). Then G = H + H′ + H* is called the decomposition of the self-complementary graph G. In part I of this paper, the fundamental properties of the three subgraphs H, H′ and H* of the self-complementary graph G are considered in detail at first. Then the method and steps of constructing self-complementary graphs are given. In part II these results will be used to study certain Ramsey number problems (see (II)). © 2000 Elsevier Science B.V. All rights reserved.