A graph and its complement with specified properties V: The self‐complement index

The self‐complement index s(G) of a graph G is the maximum order of an induced subgraph of G whose complement is also induced in G. This new graphical invariant provides a measure of how close a given graph is to being selfcomplementary. We establish the existence of graphs G of order p having s(G) = n for all positive integers n < p. We determine s(G) for several families of graphs and find in particular that when G is a tree, s(G) = 4 unless G is a star for which s(G) = 2.Peer Reviewedhttps://deepblue.lib.umich.edu/bitstream/2027.42/152737/1/mtks0025579300009943.pd