On X Free Covers

For an arbitrary graph G = (V, E), let X be a graphical property that can be possessed, or satisfied by the subsets of V. For example, being a clique (maximal complete subgraph), a maximal independent set, an edge, a closed neighborhood, a minimal dominating set, etc. Let CX ={A|A ⊆ V, |A |> 1, and A possesses or satisfies property X}. A set S is an X cover (or X free) if A ∩ S (or A ∩ (V − S)) is not empty for every A ∈ CX. Further, S is an X free cover when S is both X free and an X cover. Many vertex-partitioning problems can be viewed as that of finding an X free cover. In this paper, we present properties of X free covers and investigate the conditions for their existence in some special cases. This provides an underlying unification theory for these and other similar properties