Name
Abstract | ||
|---|---|---|
Given a system G=(G"1,G"2,...,G"m) of m graphs on the same vertex set V, define the ''joint independence number''@a"@?(G) as the maximal size of a set which is independent in all graphs G"i. Let also @c"@?(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. Konig'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 @a"@?(G"1,G"2)=@c"@?(G"1,G"2). We prove that a fractional relaxation of @a"@?, denoted by @a"@?^*, satisfies the condition @a"@?^*(G"1,G"2)=@c"@?(G"1,G"2) for any two graphs G"1,G"2, and @a"@?^*(G"1,G"2,...,G"m)2m@c"@?(G"1,G"2,...,G"m) for any m2 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 @a"@?^*(G"1,G"2,...,G"m)=@c"@?^*(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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.jctb.2008.02.001 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
collective domination number,convex hull,characteristic vector,graphs g,joint independence number,m graph,domination duality,independent set,v. konig,minimal number,system g,domination number,satisfiability,independence,simplicial complex | Discrete mathematics,Combinatorics,Disjoint sets,Matroid intersection,Vertex (geometry),Duality (mathematics),Convex hull,Duality (optimization),Function composition,Domination analysis,Mathematics | Journal |
Volume | Issue | ISSN |
98 | 6 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ron Aharoni | 1 | 380 | 66.56 |
| Eli Berger | 2 | 182 | 52.72 |
| Ron Holzman | 3 | 287 | 43.78 |
| Ori Kfir | 4 | 4 | 0.91 |