圖的Fractional邊全控制

徐保根，趙麗鑫，鄒 妍

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

圖的Fractional邊全控制

徐保根，趙麗鑫，鄒 妍

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

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

Fractional邊全控制函數(shù)；Fractional邊全控制數(shù)；Fractional邊全包裝函數(shù)；Fractional邊全包裝數(shù)

1 引言及定義

本文中所指的圖均為無向簡單圖,符號(hào)和術(shù)語同于文獻(xiàn)[1-2]。

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

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

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

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

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

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

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

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

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

2 主要結(jié)果及證明

[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].武漢，華中科技大學(xué)出版社，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

(責(zé)任編輯 姜紅貴)

2015－05－03

國家自然科學(xué)基金項(xiàng)目（11361024）；江西省高校科技落地計(jì)劃項(xiàng)目（KJLD12067）

徐保根（1963—），男，教授，主要研究方向?yàn)閳D論及其應(yīng)用。