有向图的k-彩虹控制数的界
|
摘要
设γ_(rk)(D)是有向图D的k-彩虹控制数。用构造的方法得到有向图的k-彩虹控制数的一些上下界,这些界与图的顶点数、最大出度、罗马控制数等密切相关;给出γrk(D)=k的充分必要条件,利用概率方法得到了有向图的k-彩虹控制数的一个上界。
Let γ_(rk)( D) be the k-rainbow domination number of a digraph D. The upper and lower bounds on the k-rainbow domination number of digraphs are found by construction methods,which are closely related to the number of vertices,maximum out-degree,Roman domination number,etc. And the sufficient and necessary conditions of γrk( D) = k are given. Moreover,an upper bound on the k-rainbow domination number of digraphs is found by probability method.
Let γ_(rk)( D) be the k-rainbow domination number of a digraph D. The upper and lower bounds on the k-rainbow domination number of digraphs are found by construction methods,which are closely related to the number of vertices,maximum out-degree,Roman domination number,etc. And the sufficient and necessary conditions of γrk( D) = k are given. Moreover,an upper bound on the k-rainbow domination number of digraphs is found by probability method.
引文
[1]DEHGARDI N,SHEIKHOLESLAMI S M,KHODKAR A.Bounding the paired-domination number of a tree in terms of its annihilation number[J].Filomat,2014,28:523-529.
[2]KWON Y S,LEE J.Perfect domination sets in Cayley graphs[J].Discrete Applied Mathematics,2014,162:259-263.
[3]AHANGAR H A,AMJADI J,SHEIKHOLESLAMI S M,et al.Signed Roman edge domination numbers in graphs[J].Journal of Combinatorial Optimization,2016,31(1):333-346.
[4]LIU C H,CHANG G J.Roman domination on strongly chordal graphs[J].Journal of Combinatorial Optimization,2013,26:608-619.
[5]HAO G,QIAN J.On the sum of out-domination number and in-domination number of digraphs[J].Ars Combinatoria,2015,119:331-337.
[6]CARO Y,HENNING M A.Directed domination in oriented graphs[J].Discrete Applied Mathematics,2012,160(7-8):1053-1063.
[7]郝国亮,钱建国.有向图出控制数与入控制数的和[J].厦门大学学报(自然科学版),2015,54(3):351-353.
[8]KOLTUN V,PAPADIMITRIOU C H.Approximately dominating representatives[J].Theoretical Computer Science,2007,371(3):148-154.
[9]WU J.Extended dominating-set-based routing in ad hoc wireless networks with unidirectional links[J].IEEE Transactions on Parallel Distributed Systems,2002,13(9):866-881.
[10]AMJADI J,BAHREMANDPOUR A,SHEIKHOLESLAMI S M,et al.The rainbow domination number of a digraph[J].Kragujevac Journal of Mathematics,2013,37(2):257-268.
[11]FU Y.Dominating set and converse dominating set of a directed graph[J].American Mathematical Monthly,1968,75(8):861-863.
[12]HAYNES T W,HEDETNIEMI S T,SLATER P J.Domination in graphs:advanced topics[M].New York:Marcel Dekker Incorporation,1998.
[2]KWON Y S,LEE J.Perfect domination sets in Cayley graphs[J].Discrete Applied Mathematics,2014,162:259-263.
[3]AHANGAR H A,AMJADI J,SHEIKHOLESLAMI S M,et al.Signed Roman edge domination numbers in graphs[J].Journal of Combinatorial Optimization,2016,31(1):333-346.
[4]LIU C H,CHANG G J.Roman domination on strongly chordal graphs[J].Journal of Combinatorial Optimization,2013,26:608-619.
[5]HAO G,QIAN J.On the sum of out-domination number and in-domination number of digraphs[J].Ars Combinatoria,2015,119:331-337.
[6]CARO Y,HENNING M A.Directed domination in oriented graphs[J].Discrete Applied Mathematics,2012,160(7-8):1053-1063.
[7]郝国亮,钱建国.有向图出控制数与入控制数的和[J].厦门大学学报(自然科学版),2015,54(3):351-353.
[8]KOLTUN V,PAPADIMITRIOU C H.Approximately dominating representatives[J].Theoretical Computer Science,2007,371(3):148-154.
[9]WU J.Extended dominating-set-based routing in ad hoc wireless networks with unidirectional links[J].IEEE Transactions on Parallel Distributed Systems,2002,13(9):866-881.
[10]AMJADI J,BAHREMANDPOUR A,SHEIKHOLESLAMI S M,et al.The rainbow domination number of a digraph[J].Kragujevac Journal of Mathematics,2013,37(2):257-268.
[11]FU Y.Dominating set and converse dominating set of a directed graph[J].American Mathematical Monthly,1968,75(8):861-863.
[12]HAYNES T W,HEDETNIEMI S T,SLATER P J.Domination in graphs:advanced topics[M].New York:Marcel Dekker Incorporation,1998.