Embedding graphs of small size (Q1329826)

An embedding \(\sigma\) of a graph \(G\) into its complement \(\overline G\) is a permutation of \(V(G)\) such that if \(xy\in E(G)\) then \(\sigma(x)\sigma(y)\in E(\overline G)\). \textit{D. Burns} and \textit{S. Schuster} [J. Graph Theory 1, 277-279 (1977; Zbl 0375.05046)] proved that if \(G\) is a graph of order \(n\) and \(| E(G)|\leq n- 2\), then \(G\) can be embedded into its complement \(\overline G\). This theorem had been generalized/improved in several different directions. This paper gives four further generalizations/improvements.