Jiaofeng Pan, Yu-Liang Wu, et al.
Integration, the VLSI Journal
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.
Jiaofeng Pan, Yu-Liang Wu, et al.
Integration, the VLSI Journal
Shen Lin, C.K. Wong
Annual ASIC Conference and Exhibit 1993
Charles Chiang, Majid Sarrafzadeh, et al.
International Journal of Circuit Theory and Applications
A. Albrecht, S.K. Cheung, et al.
Mathematics and Computers in Simulation