Some Results on Packing Graphs in their Complements

Abstract

A supergraph $H$ of a graph $G$ is called tree-covered if $H–E(G)$ consists of exactly $|V(G)|$ vertex-disjoint trees, with each tree having exactly one point in common with $G$. In this paper, we show that if a graph $G$ can be packed in its complement and if $H$ is a tree-covered supergraph of $G$, then $G$ itself is self-packing unless $H$ happens to be a member of a specified class of graphs. This is a generalization of earlier results that almost all trees and unicyclic graphs can be packed in their complements.