關(guān)于圖的負(fù)k-子確定數(shù)的上界

喬麗娜，陳學(xué)剛

（華北電力大學(xué)數(shù)理學(xué)院，北京 102206）

本文所指的圖均為無(wú)向簡(jiǎn)單圖。設(shè)G=（V,E）為一個(gè)圖，V和E分別表示圖G的頂點(diǎn)集和邊集。對(duì)任意的v∈V，N（v）和d（v）分別表示頂點(diǎn)v在圖G中的開(kāi)鄰域和度數(shù)，即N（v）={u∈V|uv∈E} ，d（v）=|N（v）|。令δ和Δ分別表示圖G的最小度與最大度。圖G是r-正則的，如果對(duì)于任意頂點(diǎn)v∈V，都有d（v）=r[1]。

近些年來(lái)，圖的控制理論的研究?jī)?nèi)容越來(lái)越豐富，各種控制概念相繼產(chǎn)生，其中圖的符號(hào)控制數(shù)就是圖的控制理論中的一個(gè)重要參數(shù)。圖的符號(hào)控制的概念是由Dunbar等人在文獻(xiàn)[2]中提出，以后又有不少國(guó)內(nèi)外學(xué)者定義了圖的符號(hào)控制參數(shù)的其他形式，研究成果不斷豐富[3-6]。Harris等人在文獻(xiàn)[7]中將符號(hào)全控制數(shù)引申為全k-子控制數(shù)，在此基礎(chǔ)上Ghameshlou等人在文獻(xiàn)[8]中定義了負(fù)k-子確定數(shù)。

1 定義及定理

2 主要結(jié)論

由此，我們可以看出，當(dāng)G不是正則圖時(shí)，定理2.1給出的界要比定理1.2給出的界小；當(dāng)G為正則圖時(shí)，兩定理給出的界是相等的。

在定理2.3的基礎(chǔ)上，如果每一點(diǎn)的度數(shù)都是偶數(shù)，我們可以得到更為精確的上界。

定理2.4設(shè)G為一個(gè)n階m條邊的連通圖，并且每點(diǎn)度數(shù)均為偶數(shù)，則

顯然，我們可以看出，當(dāng)r為奇數(shù)時(shí)，推論2.5比推論1.3好。

[1]BONDY JA，MURTY U S R.圖論及其應(yīng)用[M].吳望名，李念祖，吳蘭芳，等譯.北京：科學(xué)出版社，1984.

[2]DUNBAR J E，HEDETNIEMI S T，HENNING M A，et al.Signed domination in graphs[J].Graph Theory，Combinatorics and Applications，1995（1）：311-322.

[3]徐保根.圖的控制理論[M].北京：科學(xué)出版社，2008.

[4]CHANG G J，LIAW S C，YEH H G.k-Subdomination in graphs[J].DiscreteApplied Mathematics，2002，120：55-60.

[5]KANG L，QIAO H，SHAN E，et al.Lower bounds on the minus domination and k-subdomination numbers[J].Theoretical Computer Science，2003，296：89-98.

[6]趙金鳳，徐保根.關(guān)于圖的符號(hào)邊控制數(shù)的下界[J].江西師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，34（1）：27-29.

[7]HARRIS L，HATTINGH J H，HENNING M A.Total k-subdominating functions on graphs[J].Australasian Journal of Combinatorics，2006，35：141-154.

[8]GHAMESHLOU A N，KHODKAR A，SAEI R，et al.Negativek-Subdecision numbers in graphs[J].AKCE International Journal of Graphs and Combinations，2009，6（3）：361-371.