# Rall, Douglas F.; matematični kolokvij oktober 2004

## How close is a graph to being self-complementary?

Douglas F. Rall

Furman University, ZDA

14 oktober 2004

The complement, $\overline{H}$, of a simple graph H has the same vertex set as H, and two vertices are adjacent in $\overline{H}$ precisely when they are not adjacent in H. A graph is said to be self-complementary if it is isomorphic to its complement. For a given finite graph G we are interested in how close G is to being self-complementary. We define a graphical invariant that measures this closeness and establish bounds on the invariant in terms of the order of G. By appealing to structural characteristics of G (for example, the existence of a certain type of automorphism) we are able to substantially narrow the range of values of this invariant. For some common classes of graphs (for example, cycles, paths, grids and hypercubes) we show the invariant can assume one of only several values.