關(guān)于圖的反符號路控制研究

孔祥陽,徐保根,羅 茜,陳 悅

(華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院,江西南昌 330013)

關(guān)于圖的反符號路控制研究

孔祥陽,徐保根,羅 茜,陳 悅

(華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院,江西南昌 330013)

引入了反符號路控制的概念,得到了任一圖G的反符號路控制數(shù)γ′rP(G)的若干上界,并確定了一些特殊圖的反符號路控制數(shù)的確切值.

符號路控制函數(shù);符號路控制數(shù);反符號路控制函數(shù);反符號路控制數(shù)

0 引言

1996年,加拿大著名圖論專家 Cockayne等人引入了圖的許多不同類型的控制概念及其變化形式[1]. 1998年,美國圖論學(xué)者 Haynes等人出版了專著[2],系統(tǒng)地總結(jié)了近些年圖論中關(guān)于圖的點(diǎn)控制問題方面的一些重要研究成果.為了進(jìn)一步豐富和完善圖的控制理論內(nèi)容,我們從對圖的點(diǎn)控制問題的研究轉(zhuǎn)向?qū)D的邊控制問題的研究,并取得了一些研究成果,例如圖的符號邊控制及其變化形式[3-5]、反符號邊控制[6]等.

本文所用到的符號和術(shù)語若無特別說明則均與文獻(xiàn)[7]相同,并且僅考查無向簡單圖.

設(shè)G是一個非空圖,如果e∈E(G),那么NG(e)表示G中和e相鄰的邊的集合,并稱為邊e的邊鄰域. NG[e]=NG(e)∪{e}稱為e的閉邊鄰域.為方便敘述,分別將NG(e)和NG[e]簡記為N(e)和N[e].

設(shè)G=(V,E)是一個圖,G的兩個頂點(diǎn)u和v是連通的,如果在G中存在(u,v)路.連通是頂點(diǎn)集V上的一個等價關(guān)系,從而可將V劃分成一些等價類.設(shè)V的所有不同的等價類為Vi(1≤i≤k),則稱子圖G[Vi] (1≤i≤k)為G的連通分支,并記G的分支個數(shù)為ω(G).若P=(v1v2…vt)為圖G中的一條路,如果G[V(P)]= P,則稱P為G的一條無弦路或?qū)С雎?若P為圖G的一條無弦路,G中沒有更長的無弦路包含P,則稱P為圖G的一條極路.對于在圖G=(V,E)上定義的函數(shù)f:E→R和E的子集S?E(G),記f(S) =∑e∈S

f(e).

1 相關(guān)定義及引理

G的反符號路控制函數(shù)}.對于n空圖G=Kn,定義γ′rP)=0.

引理 1對任意兩個點(diǎn)不相交的圖G和H,則有γ′rP(G∪H)=γ′rP(G)+γ′rP(H).

引理 2對任意一個圖G,都有γ′rP(G)≡|E(G)|(mod 2).

2 一般圖的反符號路控制數(shù)的上界

定理1 記為將星圖的每個分支分別細(xì)分l1,l2,…,ln次所得到的圖,則有

將(1),(2)式結(jié)合可得結(jié)論成立.

3 特殊圖的反符號路控制數(shù)

證明(Ⅰ)由定義 2不難驗證該結(jié)論成立.

(Ⅱ)由定理 3和(Ⅰ)知該結(jié)論成立.

綜上可得定理結(jié)論成立.

(Ⅳ)由定理 3和(Ⅲ)知該結(jié)論成立.

[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] 徐保根,李春華.圖的符號星控制數(shù)[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),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] 徐保根.關(guān)于圖的反符號邊控制[J].華東交通大學(xué)學(xué)報,2007,24(5):144-147.

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

[8] 徐保根.關(guān)于圖的符號路控制數(shù)[J].華東交通大學(xué)學(xué)報,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

國家自然科學(xué)基金 (11061014);江西省教育廳科研項目 (GJJ09215)

孔祥陽(1985—),男,河南平頂山人,華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院在讀碩士研究生,研究方向:圖的控制理論.