Independence—domination duality

AbstractGiven a system G=(G1,G2,…,Gm) 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 Gi. 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 Gi, whose union is V. König's classical duality theorem can be stated as saying that if m=2 and both graphs G1,G2 are unions of disjoint cliques then α∩(G1,G2)=γ∪(G1,G2). We prove that a fractional relaxation of α∩, denoted by α∩∗, satisfies the condition α∩∗(G1,G2)⩾γ∪(G1,G2) for any two graphs G1,G2, and α∩∗(G1,G2,…,Gm)>2mγ∪(G1,G2,…,Gm) for any m>2 and all graphs G1,G2,…,Gm. 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 α∩∗(G1,G2,…,Gm)⩾γ∪∗(G1,G2,…,Gm) 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