图的符号星k控制数

徐保根,李春华

(华东交通大学数学系,江西南昌 330013)

图的符号星k控制数

徐保根,李春华

(华东交通大学数学系,江西南昌 330013)

引入了图的符号星k控制的概念.设G=(V,E)是一个图,一个函数f:E→{−1,+1},如果Pe∈E[v]f(e)≥1对于至少k个顶点v∈V(G)成立,则称f为图G的一个符号星k控制函数,其中E(v)表示G中与v点相关联的边集.图G的符号星k控制数定义为为图G的符号星k控制函数}.在本文中,我们主要给出了一般图的符号星k控制数的若干下界,推广了关于符号星控制的一个结果,并确定路和圈的符号星k控制数.

符号星k控制函数;符号星k控制数;符号星控制函数;符号星控制数

1 引言及定义

本文所指的图均为无向简单图,文中未说明的符号和术语同文[1].

设G=(V,E)为一个图,对于任意u∈V(G),则NG(u)为u点在G中的邻域,dG(u)= |NG(v)|为u点在G中的度,NG[u]=NG(u)∪{u}为u点在G中的闭邻域.若v∈V(G),则EG(v)表示G中与v点相关联的边集,称为v点在G中的关联边集.若e∈E(G),则NG(e)表示G中与e边相邻的边集,称为e边在G中的边邻域,并且NG[e]=NG(e)∪{e}为边e在G中的闭边邻域.为了方便,在不混淆情况下,EG(v),NG(u),NG[u],dG(u),NG(e)和NG[e]分别简记为E(v),N(u),N[u],d(u),N(e)和N[e].∆(G)和δ(G)分别为图G的最大度和最小度.

近些年来,图的控制理论研究内容越来越丰富.加拿大著名图论专家Cockayne等[2]先后引入了图的许多不同类型的控制概念及其变化形式.1998年美国图论学者Haynes等人出版了两部专著[34],较为系统地综述了近期的一些主要研究成果.然而值得注意的是:几乎所有的概念和结果都是针对图的点控制而言,很少涉及图的边控制问题.为了更进一步丰富和完善图的控制理论内容,我们已将图的点控制概念转向研究图的边控制问题,并获得了初步的研究成果,如符号边控制[56]、符号星控制[67]和符号圈控制[8]等.然而,图的边控制中存在许多未解决的问题的猜想,它们不仅与一些实际问题相联系(如局部占优设计问题等),而且与某些特殊的符号边控制相关.为此我们将引入图的符号星控制和符号星k控制概念.

设G=(V,E)为一个图,对于一个实值函数f:E→R和一个子集S⊆E(G),则记f(S)=Pe∈Sf(e).

2 主要结论及其证明

主要是给出一般图的符号星k控制数的三个下界,并确定n阶路Pn和n阶圈Cn的符号星k控制数.

定理1对于任意n阶无孤立点的图G,1≤k≤n,则有

其中∆=∆(G)和δ=δ(G)分别为图G的最大度和最小度.

[1]Bondy J A,Murty V S R.Graph Theory with Applications[M].Amsterdam:Elsevier,1976.

[2]Cockayne E J,Mynhart C M.On a generalization of signed domination functions of graphs[J].Ars.Combin., 1996,43:235-245.

[3]Haynes T W,Hedetniemi S T,Slater P J.Domination in Graphs[M].New York:Marcel Dekker,INC,1998.

[4]Haynes T W,Hedetniemi S T,Slater P J.Fundamental of Domination in Graphs[M].New York:Marcel Dekker,INC,1998.

[5]XU Baogen.On signed edge domination numbers of graphs[J].Discrete Math.,2001,239:179-189.

[6]Xu Baogen.On edge domination numbers of graphs[J].Discrete Math.,2005,294:311-316.

[7]Xu Baogen.Two classes of edge domination in graphs[J].Discrete Appl.Math.,2006,154:1541-1546.

[8]Xu Baogen.On signed cycle domination numbers of graphs[J].Discrete Math.,2009,309:1007-1012.

On signed star k domination numbers of graphs

XU Bao-gen,LI Chun-hua

(Department of Mathematics,East China Jiaotong University,Nanchang330013,China)

In this paper,we introduce the concept of signed star k domination in graphs.Let G=(V,E) be a graph,a function f:E→{−1,+1}is said to be a signed star k dominating function(SSkDF)of G if Pe∈E[v]f(e)≥1 holds for at least k vertices v∈V,where E(v)denotes the set of edges incident with v.The signed star k domination number of is defined as(G)=min{Pe∈E[G]f(e)∣f is an SSkDF of G}.In this paper we obtain some lower bounds of(G)for general graphs G,generalize a result about the signed star domination,and determine the signed star k domination numbers for the path and cycle of order n.

signed star k dominating function,signed star k domination number,signed star dominating function,signed star domination number

O157.5

A

1008-5513(2009)04-0638-04

2008-02-10.

国家自然科学基金(10661007),江西省自然科学基金(2007GZS0715),江西省教育厅科研项目(GJJ09215),华东交通大学科研基金(01308136).

徐保根(1963-),硕士,教授,研究方向：图论与组合数学.

2000MSC:05C15