Independence—domination duality

Given a system G = ( G 1 , G 2 , … , G m ) of m graphs on the same vertex set V, define the “joint independence number” α ∩ ( G ) as the maximal size of a set which is independent in all graphs G i . Let also γ ∪ ( G ) be the “collective domination number” of the system, which is the minimal number of neighborhoods, each taken from any of the graphs G i , whose union is V. Königʹs classical duality theorem can be stated as saying that if m = 2 and both graphs G 1 , G 2 are unions of disjoint cliques then α ∩ ( G 1 , G 2 ) = γ ∪ ( G 1 , G 2 ) . We prove that a fractional relaxation of α ∩ , denoted by α ∩ ∗ , satisfies the condition α ∩ ∗ ( G 1 , G 2 ) ⩾ γ ∪ ( G 1 , G 2 ) for any two graphs G 1 , G 2 , and α ∩ ∗ ( G 1 , G 2 , … , G m ) > 2 m γ ∪ ( G 1 , G 2 , … , G m ) for any m > 2 and all graphs G 1 , G 2 , … , G m . We prove that the convex hull of the (characteristic vectors of the) independent sets of a graph contains the anti-blocker of the convex hull of the non-punctured neighborhoods of the graph and vice versa. This, in turn, yields α ∩ ∗ ( G 1 , G 2 , … , G m ) ⩾ γ ∪ ∗ ( G 1 , G 2 , … , G m ) as well as a dual result. All these results have extensions to general simplicial complexes, the graphical results being obtained from the special case of the complexes of independent sets of graphs.