Rainbow Domination and Related Problems on Some Classes of Perfect Graphs

Abstract : Let $k \in \mathbb {N}$ and let G be a graph. A function $f: V(G) \rightarrow 2^{[k]}$ is a rainbow function if, for every vertex x with $f(x)=\varnothing $f(x)=∅, $f(N(x)) =[k]$, where [k] denotes the integers ranging from 1 to k. The rainbow domination number $\gamma _{kr}(G)$ is the minimum of $\sum _{x \in V(G)} |f(x)|$ over all rainbow functions. We investigate the rainbow domination problem for some classes of perfect graphs.
Type de document :
Communication dans un congrès
Mohammed Taghi Hajiaghayi; Mohammad Reza Mousavi. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. Lecture Notes in Computer Science, LNCS-9541, pp.121-134, 2016, Topics in Theoretical Computer Science. 〈10.1007/978-3-319-28678-5_9〉
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01446271
Contributeur : Hal Ifip <>
Soumis le : mercredi 25 janvier 2017 - 16:53:25
Dernière modification le : lundi 15 janvier 2018 - 11:47:14
Document(s) archivé(s) le : mercredi 26 avril 2017 - 15:16:53

Fichier

 Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Wing-Kai Hon, Ton Kloks, Hsiang-Hsuan Liu, Hung-Lung Wang. Rainbow Domination and Related Problems on Some Classes of Perfect Graphs. Mohammed Taghi Hajiaghayi; Mohammad Reza Mousavi. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. Lecture Notes in Computer Science, LNCS-9541, pp.121-134, 2016, Topics in Theoretical Computer Science. 〈10.1007/978-3-319-28678-5_9〉. 〈hal-01446271〉

Partager

Métriques

Consultations de la notice

47