Rainbow domination and related problems on some classes of perfect graphs

DOI10.1007/978-3-319-28678-5_9MaRDI QIDQ2798024zbMATH OpenOpenAlexFDO

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

Publication date 1 April 2016

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

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

zbMATH Keywords

rainbow domination problem

Mathematics Subject Classification ID

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

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.

Recommendations

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

Cited in

(8)

• Rainbow domination numbers on graphs with given radius
• Rainbow domination in graphs
• On the thinness and proper thinness of a graph
• On the \(k\)-rainbow domination in graphs with bounded tree-width
• Rainbow perfect domination in lattice graphs
• Rainbow domination in graphs
• Rainbow domination and related problems on strongly chordal 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)