Independence-domination duality in weighted graphs

DOI10.1016/J.DISC.2018.05.005zbMATH Open1388.05081arXiv1703.03320OpenAlexW2743933138MaRDI QIDQ1637152FDOQ1637152

Authors: Ron Aharoni, Irina Gorelik 

Publication date: 7 June 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Given a partition $mathcalV=(V_1,ldots,V_m)$ of the vertex set of a graph $G$, an {em independent transversal} (IT) is an independent set in $G$ that contains one vertex from each $V_i$. A {em fractional IT} is a non-negative real valued function on $V(G)$ that represents each part with total weight at least $1$, and belongs as a vector to the convex hull of the incidence vectors of independent sets in the graph. It is known that if the domination number of the graph induced on the union of every $k$ parts $V_i$ is at least $k$, then there is a fractional IT. We prove a weighted version of this result. This is a special case of a general conjecture, on the weighted version of a duality phenomenon, between independence and domination in pairs of graphs.

Full work available at URL: https://arxiv.org/abs/1703.03320

Recommendations

• Weighted domination of independent sets
• Independent systems of representatives in weighted graphs
• Independent transversal domination in graphs
• The independent transversal dombondage number of a graph
• Independence-domination duality

zbMATH Keywords

transversaldominationweighted graphjoint independencecollective domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Independent systems of representatives in weighted graphs
• A condition for matchability in hypergraphs
• Independence-domination duality

Cited In (7)

• Independence-domination duality
• The independence numbers of weighted graphs with forbidden cycles
• Independent domination versus weighted independent domination
• Title not available (Why is that?)
• On dp-minimality, strong dependence and weight
• Weighted domination in triangle-free graphs
• Independent systems of representatives in weighted graphs

This page was built for publication: Independence-domination duality in weighted graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1637152)