完全多部图的符号罗马控制数
|
摘要
设图G=(V,E)是一个简单无向图,若实值函数f:V→{-1,1,2}满足以下两个条件:(i)对于任意v∈V,均有∑_(u∈N[v])f(u)≥1成立;(ii)任意v∈V,若f(v)=-1,则存在一个与v相邻的顶点u∈V,满足f(u)=2,则称该函数为图G的符号罗马控制函数.定义图的符号罗马控制数为γSR(G)=min{f(V)f是图G的符号罗马控制函数}.通过对完全多部图中的顶点数进行分类,给出了当k≥3时,完全多部图K(n_1,…,n_i,…,n_k)的符号罗马控制数的准确值.
A signed Roman domination function, of a simple undirected graph G=(V,E)is a function f :V→{-1,1,2} satisfying the conditions that (i)∑u∈N[v]f(u)≥1 for any v∈V, and(ii)every vertex v for which f(v)=-1 is adjacent to a vertex u for which f(u)=2. The signed roman domination number of G is γSR(G)=min{f(V) f is the signed roman domination of G}. In this paper, we compute the exact values of the signed roman domination numbers of complete multi-partite graph when k>=3, through classification the vertex of G.
A signed Roman domination function, of a simple undirected graph G=(V,E)is a function f :V→{-1,1,2} satisfying the conditions that (i)∑u∈N[v]f(u)≥1 for any v∈V, and(ii)every vertex v for which f(v)=-1 is adjacent to a vertex u for which f(u)=2. The signed roman domination number of G is γSR(G)=min{f(V) f is the signed roman domination of G}. In this paper, we compute the exact values of the signed roman domination numbers of complete multi-partite graph when k>=3, through classification the vertex of G.
引文
[1]BONDY J A,MURTY V S R.Graph theory with applications[M].Amsterdam:Elsevier,1976.
[2]COCKAYNE E J,DREYERJR P A,HEDETNIEMI S M,et al.Roman domination in graphs[J].Discrete Math,2004,278(1/2/3):11-22.
[3]CHELLALI M,HAYNES T W,HEDETNIEMI S M,et al.A Roman domination chain[J].Graphs Combin,2016,32(1):79-92.
[4]AHANGAR H A,HENNING M A,LWENSTEIN C,et al.Signed Roman domination in graphs[J].J Comb Optim,2013,308(4):2313-2318.
[5]AHANGAR H A,HENNING M A,LWENSTEIN C,et al.Signed Roman domination in graphs[J].J Comb Optim,2014,27(2):241-255.
[6]SHEIKHOLESLAMI S M,VOLKMANN L.Signed Roman domination in digraphs[J].J Comb Optim,2015,30(3):456-467.
[7]HENNING M A,VOLKMAN L.Signed Roman k-domination in graphs[J].Graphs Combin,2016,32(1):175-190.
[8]张立贤.图的参数控制研究[D].浙江:浙江师范大学,2015.
[9]张立贤,吕新中.图的逆罗马控制数[J].兰州文理学院学报(自然科学版),2015,29(1):5-11.
[10]曹惠萍.若干图类的全符号控制数的研究[D].大连:大连海事大学,2016.
[2]COCKAYNE E J,DREYERJR P A,HEDETNIEMI S M,et al.Roman domination in graphs[J].Discrete Math,2004,278(1/2/3):11-22.
[3]CHELLALI M,HAYNES T W,HEDETNIEMI S M,et al.A Roman domination chain[J].Graphs Combin,2016,32(1):79-92.
[4]AHANGAR H A,HENNING M A,LWENSTEIN C,et al.Signed Roman domination in graphs[J].J Comb Optim,2013,308(4):2313-2318.
[5]AHANGAR H A,HENNING M A,LWENSTEIN C,et al.Signed Roman domination in graphs[J].J Comb Optim,2014,27(2):241-255.
[6]SHEIKHOLESLAMI S M,VOLKMANN L.Signed Roman domination in digraphs[J].J Comb Optim,2015,30(3):456-467.
[7]HENNING M A,VOLKMAN L.Signed Roman k-domination in graphs[J].Graphs Combin,2016,32(1):175-190.
[8]张立贤.图的参数控制研究[D].浙江:浙江师范大学,2015.
[9]张立贤,吕新中.图的逆罗马控制数[J].兰州文理学院学报(自然科学版),2015,29(1):5-11.
[10]曹惠萍.若干图类的全符号控制数的研究[D].大连:大连海事大学,2016.