Weighted domination of independent sets

DOI10.1007/S00373-019-02024-3MaRDI QIDQ2000566zbMATHOpenAlexFDO

Authors Irina Gorelik, Ron Aharoni

Publication date 28 June 2019

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

independencetreeschordal graphsdomination

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: The {em independent domination number} $gamm{a}^i(G)$ of a graph $G$ is the maximum, over all independent sets $I$, of the minimal number of vertices needed to dominate $I$. It is known cite{abz} that in chordal graphs $gamm{a}^i$ is equal to $gamma$, the ordinary domination number. The weighted version of this result is not true, but we show that it does hold for interval graphs, and for the intersection (that is, line) graphs of subtrees of a given tree, where each subtree is a single edge.

Recommendations

• scientific article; zbMATH DE number 1743970
• A unified approach to domination problems on interval graphs
• Algorithmic results of independent \(k\)-domination on weighted graphs
• scientific article; zbMATH DE number 2065948
• On weak domination in graphs

Cites work

• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A tree version of Kőnig's theorem
• Hall's theorem for hypergraphs
• The clique complex and hypergraph matching
• The intersection graphs of subtrees in trees are exactly the chordal graphs

Cited in

(8)

• scientific article; zbMATH DE number 1743970 (Why is no real title available?)
• Independent domination versus weighted independent domination
• The weighted independent domination problem is NP-complete for chordal graphs
• Approximating weighted neighborhood independent sets
• scientific article; zbMATH DE number 1150277 (Why is no real title available?)
• Independence-domination duality in weighted graphs
• scientific article; zbMATH DE number 2065948 (Why is no real title available?)
• Algorithmic results of independent \(k\)-domination on weighted graphs

This page was built for publication: Weighted domination of independent sets

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