Rainbow domination and related problems on some classes of perfect graphs

DOI10.1007/978-3-319-28678-5_9zbMATH Open1478.05104arXiv1502.07492OpenAlexW1538418774MaRDI QIDQ2798024FDOQ2798024

Ton Kloks, Wing-Kai Hon, Hung-Lung Wang, Hsiang-Hsuan Liu

Publication date: 1 April 2016

Published in: Topics in Theoretical Computer Science (Search for Journal in Brave)

Abstract: Let $kinmathbbN$ and let $G$ be a graph. A function $f:V(G)ightarrow{2}^{[k]}$ is a rainbow function if, for every vertex $x$ with $f(x)=emptyset$, $f(N(x))=[k]$. The rainbow domination number $gamm{a}_{kr}(G)$ is the minimum of $su{m}_{xinV(G)}|f(x)|$ over all rainbow functions. We investigate the rainbow domination problem for some classes of perfect graphs.

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

Recommendations

• Rainbow domination in graphs
• Rainbow domination in graphs
• General bounds on rainbow domination numbers
• Rainbow domination on trees
• \(k\)-rainbow domatic numbers

zbMATH Keywords

rainbow domination problem

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Perfect graphs (05C17)

Cited In (6)

• On the k-rainbow domination in graphs with bounded tree-width
• Rainbow domination in graphs
• Rainbow Domination in Graphs
• On the thinness and proper thinness of a graph
• Rainbow perfect domination in lattice graphs
• Roman \(\{k\}\)-domination in trees and complexity results for some classes of graphs

This page was built for publication: Rainbow domination and related problems on some classes of perfect graphs

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