Almost Selfcomplement Graphs \(I\)

The concept of self-complementary (s.c.) graphs is extended to almost self-complementary graphs. We define an \(n\)-vertex graph to be almost self-complementary (a.s.c.) if it is isomorphic to its complement with respect to \(K_n – e\), the complete graph with one edge removed. A.s.c. graphs with \(n\) vertices exist if and only if \(n \equiv 2\) or \(3 \pmod{4}\), i.e., precisely when s.c. graphs do not exist. We investigate various properties of a.s.c. graphs.