徐保根,李春華

(華東交通大學(xué)數(shù)學(xué)系,江西南昌 330013)

圖的符號(hào)星k控制數(shù)

徐保根,李春華

(華東交通大學(xué)數(shù)學(xué)系,江西南昌 330013)

引入了圖的符號(hào)星k控制的概念.設(shè)G=(V,E)是一個(gè)圖,一個(gè)函數(shù)f:E→{?1,+1},如果Pe∈E[v]f(e)≥1對(duì)于至少k個(gè)頂點(diǎn)v∈V(G)成立,則稱f為圖G的一個(gè)符號(hào)星k控制函數(shù),其中E(v)表示G中與v點(diǎn)相關(guān)聯(lián)的邊集.圖G的符號(hào)星k控制數(shù)定義為為圖G的符號(hào)星k控制函數(shù)}.在本文中,我們主要給出了一般圖的符號(hào)星k控制數(shù)的若干下界,推廣了關(guān)于符號(hào)星控制的一個(gè)結(jié)果,并確定路和圈的符號(hào)星k控制數(shù).

符號(hào)星k控制函數(shù);符號(hào)星k控制數(shù);符號(hào)星控制函數(shù);符號(hào)星控制數(shù)

1 引言及定義

本文所指的圖均為無向簡(jiǎn)單圖,文中未說明的符號(hào)和術(shù)語同文[1].

設(shè)G=(V,E)為一個(gè)圖,對(duì)于任意u∈V(G),則NG(u)為u點(diǎn)在G中的鄰域,dG(u)= |NG(v)|為u點(diǎn)在G中的度,NG[u]=NG(u)∪{u}為u點(diǎn)在G中的閉鄰域.若v∈V(G),則EG(v)表示G中與v點(diǎn)相關(guān)聯(lián)的邊集,稱為v點(diǎn)在G中的關(guān)聯(lián)邊集.若e∈E(G),則NG(e)表示G中與e邊相鄰的邊集,稱為e邊在G中的邊鄰域,并且NG[e]=NG(e)∪{e}為邊e在G中的閉邊鄰域.為了方便,在不混淆情況下,EG(v),NG(u),NG[u],dG(u),NG(e)和NG[e]分別簡(jiǎn)記為E(v),N(u),N[u],d(u),N(e)和N[e].?(G)和δ(G)分別為圖G的最大度和最小度.

近些年來,圖的控制理論研究?jī)?nèi)容越來越豐富.加拿大著名圖論專家Cockayne等[2]先后引入了圖的許多不同類型的控制概念及其變化形式.1998年美國(guó)圖論學(xué)者Haynes等人出版了兩部專著[34],較為系統(tǒng)地綜述了近期的一些主要研究成果.然而值得注意的是:幾乎所有的概念和結(jié)果都是針對(duì)圖的點(diǎn)控制而言,很少涉及圖的邊控制問題.為了更進(jìn)一步豐富和完善圖的控制理論內(nèi)容,我們已將圖的點(diǎn)控制概念轉(zhuǎn)向研究圖的邊控制問題,并獲得了初步的研究成果,如符號(hào)邊控制[56]、符號(hào)星控制[67]和符號(hào)圈控制[8]等.然而,圖的邊控制中存在許多未解決的問題的猜想,它們不僅與一些實(shí)際問題相聯(lián)系(如局部占優(yōu)設(shè)計(jì)問題等),而且與某些特殊的符號(hào)邊控制相關(guān).為此我們將引入圖的符號(hào)星控制和符號(hào)星k控制概念.

設(shè)G=(V,E)為一個(gè)圖,對(duì)于一個(gè)實(shí)值函數(shù)f:E→R和一個(gè)子集S?E(G),則記f(S)=Pe∈Sf(e).

2 主要結(jié)論及其證明

主要是給出一般圖的符號(hào)星k控制數(shù)的三個(gè)下界,并確定n階路Pn和n階圈Cn的符號(hào)星k控制數(shù).

定理1對(duì)于任意n階無孤立點(diǎn)的圖G,1≤k≤n,則有

其中?=?(G)和δ=δ(G)分別為圖G的最大度和最小度.

[1]Bondy J A,Murty V S R.Graph Theory with Applications[M].Amsterdam:Elsevier,1976.

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

[3]Haynes T W,Hedetniemi S T,Slater P J.Domination in Graphs[M].New York:Marcel Dekker,INC,1998.

[4]Haynes T W,Hedetniemi S T,Slater P J.Fundamental of Domination in Graphs[M].New York:Marcel Dekker,INC,1998.

[5]XU Baogen.On signed edge domination numbers of graphs[J].Discrete Math.,2001,239:179-189.

[6]Xu Baogen.On edge domination numbers of graphs[J].Discrete Math.,2005,294:311-316.

[7]Xu Baogen.Two classes of edge domination in graphs[J].Discrete Appl.Math.,2006,154:1541-1546.

[8]Xu Baogen.On signed cycle domination numbers of graphs[J].Discrete Math.,2009,309:1007-1012.

On signed star k domination numbers of graphs

XU Bao-gen,LI Chun-hua

(Department of Mathematics,East China Jiaotong University,Nanchang330013,China)

In this paper,we introduce the concept of signed star k domination in graphs.Let G=(V,E) be a graph,a function f:E→{?1,+1}is said to be a signed star k dominating function(SSkDF)of G if Pe∈E[v]f(e)≥1 holds for at least k vertices v∈V,where E(v)denotes the set of edges incident with v.The signed star k domination number of is defined as(G)=min{Pe∈E[G]f(e)∣f is an SSkDF of G}.In this paper we obtain some lower bounds of(G)for general graphs G,generalize a result about the signed star domination,and determine the signed star k domination numbers for the path and cycle of order n.

signed star k dominating function,signed star k domination number,signed star dominating function,signed star domination number

O157.5

A

1008-5513(2009)04-0638-04

2008-02-10.

國(guó)家自然科學(xué)基金(10661007),江西省自然科學(xué)基金(2007GZS0715),江西省教育廳科研項(xiàng)目(GJJ09215),華東交通大學(xué)科研基金(01308136).

徐保根(1963-),碩士,教授,研究方向：圖論與組合數(shù)學(xué).

2000MSC:05C15