任媛,赵凌琪,吉日木图,王妍
(1.内蒙古民族大学数学学院,内蒙古通辽市028043; 2.内蒙古民族大学计算机科学与技术学院,内蒙古通辽市028043; 3.山东水利职业学院信息工程系,山东日照276826)
两类图的符号控制数
任媛1,赵凌琪2,吉日木图1,王妍3
(1.内蒙古民族大学数学学院,内蒙古通辽市028043; 2.内蒙古民族大学计算机科学与技术学院,内蒙古通辽市028043; 3.山东水利职业学院信息工程系,山东日照276826)
图G的符号控制数(G)有着许多重要的应用背景,因而确定其精确值有重要意义.Cm表示m个顶点的圈,n−Cm和n…Cm分别表示恰有一条公共边或一个公共顶点的n个Cm的拷贝.给出了n−Cm和n…Cm的符号控制数.
图;符号控制函数;符号控制数
本文中所指的图均为无向简单图,文中未说明的符号和术语同文献[1].
近些年来,图的控制理论的研究越来越广泛,各种控制概念相继产生,例如符号边控制,符号边全控制,减控制,弱符号控制,符号星K控制等等,并获得了一些初步的研究成果[2-6],尤其是对图的符号控制,得到了许多新的结论[7-11].设图G=(V,E).v∈V,v的开邻域是与v相邻接的顶点集合,即N(v)={u|uv∈E}.称N(v)∪{v}为v的闭邻域,记为N[v].
定义1.1[7]图G=(V,E)的顶点集V上,定义一个双值函数f:V→{−1,+1},并且f[v]=f(N[v]),若在任何一个顶点v的闭邻域N[v]上函数值的和至少是1,即∀v∈V, f(N[v])≥1,则称函数f是G的一个符号控制函数.一个符号控制函数的权重是
图G的符号控制数γs(G)定义为γs(G)=min{f(V)|f是G的符号控制函数}.
定理1.1[7]对阶为n≥3的圈图
定理1.2[7]对完全图Kn,有
定理1.3[7]星图K1,m的符号控制数γs(K1,m)=m+1.
对二部图Km,n(n≥m≥2),有下面两个定理:
定理1.4[7]当m=2,3时,有
定理1.5[7]当n≥m≥4时,有
定理1.6[8]对任意正整数n≥2,扇图
定理1.7[8]对任意正整数n≥3,轮图
定理1.8[9]对于任意n阶图G,∆和δ分别为图G的最大度和最小度,则有
本文给出了n−Cm和n…Cm的符号控制数.
定理2.1对任意正整数m≥3,n≥2,有
证明令表示n−Cm中的第i个m-圈,u和v表示的两个公共顶点,n−Cm中的第i个m-圈中余下的顶点依次为
设函数f是n−Cm的一个符号控制函数,注意到:
下面分三种情况进行讨论.
情况1当m≡0(mod 3)时,考虑u和v的对称性,只需讨论下面三种情况.
情况1.1当f(u)=f(v)=−1时.
当m=3时,不满足符号控制函数的定义,故下面考虑m>3时,由
容易得到每个m-圈中余下(m−6)个顶点中分配值为−1的个数最多为现在考虑每个m-圈中余下(m−6)个顶点中分配值为−1的个数为时,下面给出此时的一个符号控制函数:
情况1.2当f(u)=−1,f(v)=+1时.
容易得到每个m-圈中余下(m−4)个顶点中分配值为−1的个数最多为现在考虑每个m-圈中余下(m−4)个顶点中分配值为−1的个数为时,下面给出此时的一个符号控制函数:
情况1.3当f(u)=f(v)=+1时.
下面讨论n−Cm(m≡0(mod 3))中满足上述条件的的个数:
由
此时,f是满足要求的、权最小的一个符号控制函数.
情况1.3.1当n≡1(mod 2)时,此时
情况1.3.2当n≡0(mod 2)时,此时
结合情况1.1,情况1.2,情况1.3,有
其中m≡0(mod 3).
情况2当m≡1(mod 3)时,考虑u和v的对称性,只需讨论下面三种情况.
情况2.1当f(u)=f(v)=−1时.
用情况1.1中同样的方法,容易得到每个m-圈中余下(m−6)个顶点中分配值为−1的个数最多为现在考虑每个m-圈中余下(m−6)个顶点中分配值为−1的个数为时,下面给出此时的一个符号控制函数:
情况2.2当f(u)=−1,f(v)=+1时.
情况2.3当f(u)=f(v)=+1时.
结合情况2.1,情况2.2,情况2.3,有
情况3当m≡2(mod 3)时,考虑u和v的对称性,只需讨论下面三种情况.
情况3.1当f(u)=f(v)=−1时.
情况3.2当f(u)=−1,f(v)=+1时.
容易得到每个m-圈中余下(m−5)个顶点中分配值为−1的个数最多为现在考虑每个m-圈中余下(m−5)个顶点中分配值为−1的个数为时,又由
此时,f是满足要求的、权最小的一个符号控制函数.
情况3.2.1当n≡1(mod 2)时,此时
情况3.2.2当n≡0(mod 2)时,此时
情况3.3当f(u)=f(v)=+1时.
结合情况3.1,情况3.2,情况3.3,有
其中m≡2(mod 3).
综上所述,对任意正整数m≥3,n≥2,
定理2.2对任意正整数m≥3,n≥2,
证明令表示n…Cm中的第i个m-圈,u表示的公共顶点,n…Cm中的第i个m-圈中余下的顶点依次为
设函数f是n…Cm的一个符号控制函数,注意到:
下面分三种情况进行讨论:
情况1当m≡0(mod 3)时.
下面给出此时的一个符号控制函数:
情况2当m≡1(mod 3)时.
情况2.1当f(u)=−1时.
容易得到每个m-圈中余下(m−5)个顶点中分配值为−1的个数最多为现在考虑每个m-圈中余下(m−5)个顶点中分配值为−1的个数为时,下面给出此时的一个符号控制函数:
情况2.2当f(u)=+1时.
由容易得到每个m-圈中余下(m−1)个顶点中分配值为−1的个数最多为现在考虑每个m-圈中余下(m−1)个顶点中分配值为−1的个数为时,下面给出此时的一个符号控制函数:
结合情况2.1,情况2.2,有
情况3当m≡2(mod 3)时.
情况3.1当f(u)=−1时.
情况3.2当f(u)=+1时.
下面讨论n…Cm(m≡2(mod 3))中满足上述条件的的个数:
由
此时,f是满足要求的、权最小的一个符号控制函数.
情况3.2.1当n≡1(mod 2)时,此时
情况3.2.2当n≡0(mod 2)时,此时
结合情况3.1,情况3.2,有
综上所述,对任意正整数m≥3,n≥2,
[1]Bondy J A,Murty U S R.Graph Theory With Applications[M].London:Macmillan,1977.
[2]Xu Baogen.On signed edge domination numbers of graphs[J].Discrete Math.,2001,239:179-189.
[3]Zhao Jinfeng,Xu Baogen.On signed edge total domination numbers of graphs[J].Journal of Mathematical Research Exposition,2011,31(2):209-214.
[4]Xu Baogen.On minus domination and signed domination in graphs[J].J.Math.Res.Exposition, 2003,23(4):586-590.
[5]尚华辉,苗连英,苗正科,等.关于图的弱符号控制数的下界[J].纯粹数学与应用数学,2010,26(4):691-695.
[6]李春华.图的符号星K控制数[J].纯粹数学与应用数学,2009,25(4):638-641.
[7]于崇智,徐保根.图的符号控制数[J].华东交通大学学报,1997,14(4):54-58,67.
[8]于崇智.图的最小符号控制函数的充要条件[J].阴山学刊,1999,15(1):5-8.
[9]徐保根,丁宗鹏,罗茜.图的符号控制数的下界[J].华东交通大学学报,2011,28(3):69-72.
[10]王军秀.特殊图类的符号控制数[J].纯粹数学与应用数学,2005,21(1):59-61.
[11]徐保根.图的控制理论[M].北京:科学出版社,2008.
Signed domination numbers for two class of graphs
Ren Yuan1,Zhao Lingqi2,Jirimutu1,Wang Yan3
(1.College of Mathematics,Inner Mongolia University for Nationalities,Tongliao028043,China; 2.College of Computer and Technology,Inner Mongolia University for Nationalities,Tongliao028043,China; 3.Department of Information Engineering,Shandong Water Polytechnic,Rizhao276826,China)
The signed domination number of a graph has its import and applying background,so it is useful to determinate the exact value of it.Cmdenotes the cycle of length m,n−Cmand n…Cmdenote the graph obtained from any n copies of Cmwhich have just one common edge and one common vertex,respectively.In this paper,we obtain the signed domination numbers of n−Cmand n…Cm.
graph,signed domination function,signed domination number
O157.5
A
1008-5513(2014)03-0271-09
10.3969/j.issn.1008-5513.2014.03.008
2012-06-07.
国家自然科学基金(61261025,61262018);内蒙古民族大学校级研究项目(NMD1104).
任媛(1987-),硕士,助教,研究方向:图论及其应用.
2010 MSC:05C78