关于图的反符号路控制研究

孔祥阳,徐保根,罗 茜,陈 悦

(华东交通大学基础科学学院,江西南昌 330013)

关于图的反符号路控制研究

孔祥阳,徐保根,罗 茜,陈 悦

(华东交通大学基础科学学院,江西南昌 330013)

引入了反符号路控制的概念,得到了任一图G的反符号路控制数γ′rP(G)的若干上界,并确定了一些特殊图的反符号路控制数的确切值.

符号路控制函数;符号路控制数;反符号路控制函数;反符号路控制数

0 引言

1996年,加拿大著名图论专家 Cockayne等人引入了图的许多不同类型的控制概念及其变化形式[1]. 1998年,美国图论学者 Haynes等人出版了专著[2],系统地总结了近些年图论中关于图的点控制问题方面的一些重要研究成果.为了进一步丰富和完善图的控制理论内容,我们从对图的点控制问题的研究转向对图的边控制问题的研究,并取得了一些研究成果,例如图的符号边控制及其变化形式[3-5]、反符号边控制[6]等.

本文所用到的符号和术语若无特别说明则均与文献[7]相同,并且仅考查无向简单图.

设G是一个非空图,如果e∈E(G),那么NG(e)表示G中和e相邻的边的集合,并称为边e的边邻域. NG[e]=NG(e)∪{e}称为e的闭边邻域.为方便叙述,分别将NG(e)和NG[e]简记为N(e)和N[e].

设G=(V,E)是一个图,G的两个顶点u和v是连通的,如果在G中存在(u,v)路.连通是顶点集V上的一个等价关系,从而可将V划分成一些等价类.设V的所有不同的等价类为Vi(1≤i≤k),则称子图G[Vi] (1≤i≤k)为G的连通分支,并记G的分支个数为ω(G).若P=(v1v2…vt)为图G中的一条路,如果G[V(P)]= P,则称P为G的一条无弦路或导出路.若P为图G的一条无弦路,G中没有更长的无弦路包含P,则称P为图G的一条极路.对于在图G=(V,E)上定义的函数f:E→R和E的子集S⊆E(G),记f(S) =∑e∈S

f(e).

1 相关定义及引理

G的反符号路控制函数}.对于n空图G=Kn,定义γ′rP)=0.

引理 1对任意两个点不相交的图G和H,则有γ′rP(G∪H)=γ′rP(G)+γ′rP(H).

引理 2对任意一个图G,都有γ′rP(G)≡|E(G)|(mod 2).

2 一般图的反符号路控制数的上界

定理1 记为将星图的每个分支分别细分l1,l2,…,ln次所得到的图,则有

将(1),(2)式结合可得结论成立.

3 特殊图的反符号路控制数

证明(Ⅰ)由定义 2不难验证该结论成立.

(Ⅱ)由定理 3和(Ⅰ)知该结论成立.

综上可得定理结论成立.

(Ⅳ)由定理 3和(Ⅲ)知该结论成立.

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

[2] Haynes TW,Hedetniemi S T,Slater P J.Domination in graphs[M].New York:MarcelDekker Inc.,1998.

[3] 徐保根,李春华.图的符号星控制数[J].纯粹数学与应用数学,2009,25(4):638-641.

[4] Xu Baogen.On signed edge domination numbers of graphs[J].DiscreteMath,2001,239(1-3):179-189.

[5] Xu Baogen.On signed cycle domination in graphs[J].DiscreteMath,2009,309(4):1007-1012.

[6] 徐保根.关于图的反符号边控制[J].华东交通大学学报,2007,24(5):144-147.

[7] Bondy J A,MurtyV S R.Graph theorywith applications[M].New York:Elsevier,1976.

[8] 徐保根.关于图的符号路控制数[J].华东交通大学学报,2006,23(4):119-121.

Research on Reverse Signed Path Dom ination in Graphs

KONG Xiang-yang,XU Bao-gen,LUO Xi,CHEN Yue

(School of Basic Science,East China Jiaotong University,Nanchang330013,China)

Introduce the concept of reverse signed path domination,get some upper bounds of the reverse signed domination numberγrP′of any graphG,and determine the exact reverse signed path domination numbers of some special graphs.

signed path dominating function;signed path domination number;reverse signed path dominating function;reverse signed path domination number

O157.5

A

1007-0834(2010)04-0003-03

10.3969/j.issn.1007-0834.2010.04.002

2010-08-26

国家自然科学基金 (11061014);江西省教育厅科研项目 (GJJ09215)

孔祥阳(1985—),男,河南平顶山人,华东交通大学基础科学学院在读硕士研究生,研究方向:图的控制理论.