International Journal of Mathematics and Mathematical Sciences
Volume 2 (1979), Issue 2, Pages 223-228

A graph and its complement with specified properties I: connectivity

Jin Akiyama1 and Frank Harary2

1Mathematics Department, Nippon Ika University, Kawasaki, Japan
2Mathematics Department, University of Michigan, Ann Arbor 48109, Michigan, USA

Received 14 November 1978

Copyright © 1979 Jin Akiyama and Frank Harary. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


We investigate the conditions under which both a graph G and its complement G¯ possess a specified property. In particular, we characterize all graphs G for which G and G¯ both (a) have connectivity one, (b) have line-connectivity one, (c) are 2-connected, (d) are forests, (e) are bipartite, (f) are outerplanar and (g) are eulerian. The proofs are elementary but amusing.