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
Jin Akiyama1
and Frank Harary2
1Mathematics Department, Nippon Ika University, Kawasaki, Japan
2Mathematics Department, University of Michigan, Ann Arbor 48109, Michigan, USA
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.