Rainbow domination and related problems on strongly chordal graphs

详细信息    查看全文

• 作者：Gerard J. Chang^a ; ^b ; ^c ; ^{gjchang@math.ntu.edu.tw} ; Bo-Jr Li^c ; ^{leebojr@gmail.com} ; Jiaojiao Wu^a ; ^{wujj0007@yahoo.com.tw}
• 关键词：Domination ; Rainbow domination ; (j ; k)(j ; k)-domination ; kk-tuple domination ; Domatic number ; Algorithm ; Strongly chordal graph ; Block graph
• 刊名：Discrete Applied Mathematics
• 出版年：2013
• 出版时间：July, 2013
• 年：2013
• 卷：161
• 期：10-11
• 页码：1395-1401
• 全文大小：403 K

文摘

This paper studies a variation of domination in graphs called rainbow domination. For a positive integer , a -rainbow dominating function of a graph is a function such that for any vertex with . The -rainbow domination number of is the minimum value of , where runs over all -rainbow dominating functions of . A related concept is as follows. A weak -dominating function of is a function such that for any vertex with . The weak -domination number of is the minimum value of , where runs over all weak -dominating functions of . In this paper, we prove that for any strongly chordal graph . Our approach is a more general setting called the -function, which leads to interesting results on other variations of domination. We also give a linear-time algorithm for finding the weak -domination numbers of block graphs.