圖的Fractional邊全控制

徐保根，趙麗鑫，鄒 妍

（華東交通大學理學院，江西 南昌 330013）

圖的Fractional邊全控制

徐保根，趙麗鑫，鄒 妍

（華東交通大學理學院，江西 南昌 330013）

設G=(V,E)是一個無孤立邊的圖，一個實值函數f:E(G)→[0,1]若對所有的邊e∈E(G)，均有成立，則稱f為圖G的一個Fractional邊全控制函數。圖G的Fractional邊全控制數定義為為圖G的一個Fractional邊全控制函數}。確定了一般圖的Fractional邊全控制數若干界限，同時也研究了幾類特殊圖Fractional邊全控制問題，給出了一些特殊圖的Fractional邊全控制數。

Fractional邊全控制函數；Fractional邊全控制數；Fractional邊全包裝函數；Fractional邊全包裝數

1 引言及定義

本文中所指的圖均為無向簡單圖,符號和術語同于文獻[1-2]。

圖的控制理論是圖論中很重要的一個分支。在圖的控制理論的發展和完善過程中，Hedetniemi S M等人首次提出并研究了圖的Fractional控制概念和性質，在當MITCHELL S和HEDETNIEMI S T引入了圖的一般邊控制的概念之后,自然產生了圖的Fractional邊控制概念，并對其進行了大量研究[3-4]。 而文獻[5]首先提出并研究了圖的符號邊控制，由此衍生到邊上的多種控制概念，如Fractional邊控制等[6]等，從而使得控制理論的研究內容和研究成果越來越豐富，本文主要給出了圖的Fractional邊全控制概念和一些主要結果。

設G=(V,E)是一個連通圖，用V(G)和E(G)分別表示G的頂點集和邊集。對于任意一條邊e∈E(G)，定義e在G中的鄰域NG[e]，表示G中與邊e相關聯的邊的集合。閉邊鄰域NG[e]=NG(e)∪{e}。NG(e)和NG[e]分別簡記為NG(e)和NG[e]。v點G在中的度記為d(V)=｜N(v)｜，并且△=△(G)和δ=δ(G)分別表示圖G中點的最大度和最小度，邊e在圖G中的邊度是指與其相連的邊的條數，記為d(e)=│N(e)│。若e=uv∈E(G)，則有d(e)=d(u)+d(v) -2。△′=△′(G)和δ′=δ′(G)和分別表示圖G中邊的最大度和最小度。

為了方便，設G=(V,E)若S?E(G)，f：E→R為一個實值函數，則記

定義1[7]設G=（V，E）是一個無孤立邊的圖，如果一個實值函數f：E→[0，1]對任意的e∈E(G)均有f（N（e））≥1成立，則稱f為圖G的一個Fractional邊全控制函數（簡稱為F-邊全控制函數）。圖G的F-邊全控制數定義為

并且稱滿足γ′ft（G）=min{f（E）的F邊全控制函數f為一個最小F-邊全控制函數。

定義2[7]設G=（V，E）是一個無孤立邊的圖，如果一個實值函數f：E→[0，1]對任意的e∈E(G)均有f（N（e））≥1成立，則稱f為圖G的一個F-邊全包裝函數。圖G的一個F-邊全包裝數定義為

并且稱滿足P′ft（G）=f（E）的F-邊全包裝函數f為一個最大F-邊全包裝函數。

在上述兩個定義中，如果將邊鄰域“N（e）”改為閉邊鄰域“N[e]”，則對應定義為F-邊控制數和F-邊包裝數。類似地，可分別定義F-點控制函數γ′ft（G）和F-點包裝數Pf（G）。Domke G S[8]等證明了γf（G）=Pft（G）對任意圖成立，這表明γ′ft（G）=P′ft（G）對任何無孤立邊的圖成立。特殊地，如果一個實值函數f：E→[0，1]滿足f（N（e））=1對任意e∈E(G)成立，則f為G的一個最小F-邊全控制函數，同時f也是圖G的一個F-邊全包裝函數，因此有下面的引理成立。

引理1 設G為一個圖，若存在一個實值函數f：E（G）→[0，1]，使得對任意的e∈E(G)均有f（N（e））=1成立，則有γ′ft（G）=f（E（G））。

2 主要結果及證明

[1]BONDYJ A，MURTY V S R.Graph Theory with Application[M].Elsevier，Amsterdam，1976.

[2]HAYNES T W，HEDETNIEMI S T，SLATER P J.Domination in Graph[M].Marcel Dekker，Inc New York，1998.

[3]HEDETNIEMI S M，HEDETNIEMI S T,WIMER T V.Linear time resource allocation algorithms for trees.Technical report URI-014,Department of Mathematics[R].Clems on University，1987.

[4]MITCHELL S，HEDETNIEMI S T.Edge domination in trees[J].Congr Numer，1977（19）：489-509.

[5]BAOGEN XU.On signed edge domination numbers of graphs[J].Discrete Math，2001（239）：179-189.

[6]ARUMUGAM S.Fractional edge domination in graphs[J].APPL ANAL Discrete Math，2009（3）：359-370.

[7]徐保根，圖的控制與染色理論[M].武漢，華中科技大學出版社，2013.

[8]DOMKE G S，HEDETNIEMI S T，LASKAR R C.Fractional packings，coverings and irredundance in graphs[J].Congr Numer，1988（66）：227-238.

Fractional Edge Total Domination Numbers in Graphs

Xu Baogen,Zhao Lixin,Zou Yan
(School of Science，East China Jiaotong University，Nanchang 330013，China)

LetG=(V,E)be a graph without isolated edges,a real functionf:E(G)→[0,1]is said to be a fractional edge total domination function(FETDF)of G ifholds for everye∈E(G)edge，then the fractional edge total domination number酌ft′(G)ofGis defined asis a FETDF of G}.This paper determines bounds for the fractional edge total domination numbers of a graph.Meanwhile,it discusses some questions on the fractional edge total domination and gives the fractional edge total domination numbers of some special graphs.

fractional edge total dominating function;fractional edge total domination number;fractional edge total packing function;fractional edge total packing number

O157.5

A

1005-0523（2015）06-0106-04

(責任編輯 姜紅貴)

2015－05－03

國家自然科學基金項目（11361024）；江西省高校科技落地計劃項目（KJLD12067）

徐保根（1963—），男，教授，主要研究方向為圖論及其應用。