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

喬麗娜，陳學剛

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

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

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

1 定義及定理

2 主要結(jié)論

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

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

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

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

[1]BONDY JA，MURTY U S R.圖論及其應用[M].吳望名，李念祖，吳蘭芳，等譯.北京：科學出版社，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].北京：科學出版社，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)于圖的符號邊控制數(shù)的下界[J].江西師范大學學報：自然科學版，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.