International Journal of Mathematics and Mathematical Sciences
Volume 2 (1979), Issue 2, Pages 223-228
doi:10.1155/S016117127900020X
A graph and its complement with specified properties I: connectivity
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.
Abstract
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.