Weighted domination of independent sets

DOI10.1007/S00373-019-02024-3zbMATH Open1416.05202arXiv1709.09889OpenAlexW2963382235MaRDI QIDQ2000566FDOQ2000566

Authors: Irina Gorelik, Ron Aharoni 

Publication date: 28 June 2019

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

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.

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

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

zbMATH Keywords

independencetreeschordal graphsdomination

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Hall's theorem for hypergraphs
• A tree version of Kőnig's theorem
• The clique complex and hypergraph matching

Cited In (7)

• Algorithmic results of independent \(k\)-domination on weighted graphs
• The weighted independent domination problem is NP-complete for chordal graphs
• Title not available (Why is that?)
• Independent domination versus weighted independent domination
• Title not available (Why is that?)
• Approximating weighted neighborhood independent sets
• Title not available (Why is that?)

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)