圖的符號星k控制數

徐保根,李春華

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

圖的符號星k控制數

徐保根,李春華

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

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

符號星k控制函數;符號星k控制數;符號星控制函數;符號星控制數

1 引言及定義

本文所指的圖均為無向簡單圖,文中未說明的符號和術語同文[1].

設G=(V,E)為一個圖,對于任意u∈V(G),則NG(u)為u點在G中的鄰域,dG(u)= |NG(v)|為u點在G中的度,NG[u]=NG(u)∪{u}為u點在G中的閉鄰域.若v∈V(G),則EG(v)表示G中與v點相關聯的邊集,稱為v點在G中的關聯邊集.若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]分別簡記為E(v),N(u),N[u],d(u),N(e)和N[e].?(G)和δ(G)分別為圖G的最大度和最小度.

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

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

2 主要結論及其證明

主要是給出一般圖的符號星k控制數的三個下界,并確定n階路Pn和n階圈Cn的符號星k控制數.

定理1對于任意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.

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

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

2000MSC:05C15