Rainbow domination and related problems on some classes of perfect graphs

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

Let k ∈ N and let G be a graph. A function f: V (G) → 2[k] is a rainbow function if, for every vertex x with f(x) = ∅, f(N(x)) = [k], where [k] denotes the integers ranging from 1 to k. The rainbow domination number γkr(G) is the minimum of Σx∈V(G) |f(x)| over all rainbow functions. We investigate the rainbow domination problem for some classes of perfect graphs.

Original languageEnglish
Title of host publicationTopics in Theoretical Computer Science -The 1st IFIP WG 1.8 International Conference, TTCS 2015, Revised Selected Papers
EditorsMohammad Taghi Hajiaghayi, Mohammad Reza Mousavi
PublisherSpringer Verlag
Pages121-134
Number of pages14
ISBN (Print)9783319286778
DOIs
Publication statusPublished - 2016
Externally publishedYes
Event1st IFIP WG 1.8 International Conference on Topics in Theoretical Computer Science, TTCS 2015 - Tehran, Iran, Islamic Republic of
Duration: 2015 Aug 262015 Aug 28

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9541
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference1st IFIP WG 1.8 International Conference on Topics in Theoretical Computer Science, TTCS 2015
Country/TerritoryIran, Islamic Republic of
CityTehran
Period2015/08/262015/08/28

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Rainbow domination and related problems on some classes of perfect graphs'. Together they form a unique fingerprint.

Cite this