国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

關(guān)于圖的集控制數(shù)

2011-07-05 11:21:12徐保根丁宗鵬
關(guān)鍵詞:圖論乘積界限

徐保根,羅 茜,丁宗鵬

(華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院江西南昌330013)

1 引言及定義

文中所指的圖均為無(wú)向簡(jiǎn)單圖,文中未說(shuō)明的符號(hào)和術(shù)語(yǔ)同文獻(xiàn)[1]。

設(shè)G為一個(gè)圖,對(duì)于任意v,則NG(v)表示v點(diǎn)在G中的鄰域,dG(v)= ||NG(v)表示v點(diǎn)在G中的度,NG[v]=NG(v)∪{v}稱(chēng)為v點(diǎn)的閉鄰域,δ和Δ分別為圖G的最小度和最大度,有時(shí),NG[v]和dG(v)分別簡(jiǎn)記為N[v]和d(v)。

設(shè)G和H為兩個(gè)點(diǎn)不交的圖,在G∪H中將G的每個(gè)頂點(diǎn)與H的每個(gè)頂點(diǎn)均鄰接起來(lái),所得的圖稱(chēng)為G與H的聯(lián)圖,記為G∨H。

對(duì)于兩個(gè)點(diǎn)不交的圖G和H,則G與H的乘積圖記為G×H,其定義為

E

設(shè)G為一個(gè)圖,D?V(G),如果對(duì)于V(G)D中的每個(gè)頂點(diǎn)v,存在u∈D,使得u與v在G中鄰接,則稱(chēng)D為G的一個(gè)控制集,容量最小的控制集包含的點(diǎn)數(shù)稱(chēng)為G的控制數(shù),記為γ(G)。

圖的控制理論是圖論中的重要分支,美國(guó)圖論學(xué)者W.T.Haynes等[2]在1998年出版的專(zhuān)著較為系統(tǒng)地綜述了這一領(lǐng)域的一些主要研究成果。在1977年,E.J.Cockayne和S.T.Hedetniemi[3]引入了圖的集控制概念并研究圖的集控制數(shù),B.Zelinka[4-5]在圖的集控制方面做了大量工作,得出了集控制數(shù)與圖的其它參數(shù)之間的關(guān)系,如集控制數(shù)與線(xiàn)性點(diǎn)蔭度的關(guān)系[4]等。

定義1[3]設(shè)G是一個(gè)圖,如果V(G)能劃分為t個(gè)兩兩不交的控制集Di(i=1,2,...,t),則稱(chēng)G有t-控制集劃分。圖G的集控制數(shù)記為d(G),其定義為:d(G)=max{t|存在G的t-控制集劃分}。

對(duì)于任何圖G,由于D=V(G)本身就是G的一個(gè)控制集,故d(G)總是存在的,并且不難證明下面的結(jié)論。

引理1[6]對(duì)任意圖G,均有d(G)≤1+δ(G)。且v1鄰接v2,或者v1=v2且u1鄰接u2}。

在本文中,我們主要研究乘積圖與聯(lián)圖的集控制問(wèn)題,給出這兩種圖集控制數(shù)的界限,并確定了一些特殊性圖的集控制數(shù),這包括Km×Kn和Pm×Pn等。

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

首先給出兩個(gè)圖的乘積圖與聯(lián)圖的集控制數(shù)的界限,然后確定Km×Kn和Pm×Pn的集控制數(shù)。定理1 對(duì)于任意n階圖G和m階圖H,均有

并且此上界和下界均是可達(dá)的。

1)先證max{n,m} ≥d(G×H),不妨設(shè)n≥m,即證n≥t。

(反證)假若n≤t-1,由定義知:V(G×H)能劃分為t個(gè)兩兩不交的控制集Di(i=1,2,…,t),即

V(G×H)=D1∪D2∪…∪Dt,并且Di∩Dj=? (1≤i≠j≤t),注意到,故上述劃分中存在一個(gè)Dk,使得

?u∈V1,v∈V2,由乘積圖的定義知:圖G×H中的點(diǎn)(u,v)不與Dk中的任何點(diǎn)相鄰,這與Dk為G×H的控制集矛盾,從而n≥t。

2)下面證明d(G×H)≥max{d(G),d(H)} 。

記d(G)=p,d(H)=q,不妨設(shè)p≥q,將V(G)劃分為p個(gè)兩兩不交的控制集Ai(i=1,2,…,p),即V(G)=A1∪A2∪…∪Ap,并且Ai∩Aj=?(1≤i≠j≤p)。

現(xiàn)將V(G×H)分成p個(gè)子集如下

由于每個(gè)Ai均是G的控制集,故每個(gè)Di均是G×H的控制集,即d(G×H)≥p。

特殊地,當(dāng)G=Kn為n階完全圖,且n≥m時(shí),定理給出的上、下界限均可達(dá)。至此,定理1證畢。

注意到d(Kn)=n,故由上述定理1可直接得到下面兩個(gè)推論。

推論1 設(shè)n和m為整數(shù),且n≥m,則對(duì)任意m階圖H,均有d(Kn×H)=n。

推論2 對(duì)于任意正整數(shù)m和n,均有d(Km×Kn)=max{m,n} 。

定理2 對(duì)于任意n階圖G和m階圖H,均有

并且此上界和下界均是可達(dá)的。

證明 不妨設(shè)n≥m。記先證d(G∨H)≥m。只需將V(G∨H)劃分為m個(gè)控制集即可,事實(shí)上,可令

可見(jiàn)上述每個(gè)Di(i=1,2,…,m)均為G∨H的控制集,即d(G∨H)≥m。

下面證明d(G∨H)≤min{m+d(G),n+d(H)} 。

由對(duì)稱(chēng)性,只需證明d(G∨H)≤m+d(G)即可。記d(G∨H)=t,d(G)=r。

(反證)假若t≥m+r+1,由定義知V(G∨H)能劃分為t個(gè)圖G∨H的控制集,即

V(G∨H)=D1∪D2∪…∪Dt,且Di∩Dj=?(1≤i≠j≤t)。注意到 |V(H)|=m,t≥m+r+1,故這些控制集中至少有r+1個(gè)控制集均不包含圖H中的點(diǎn),這r+1個(gè)控制集記為Di1,Di2,…,Di(r+1),它們均不包含圖H中的點(diǎn),且均為G∨H的控制集,故每個(gè)Dij(j=1,2,…,r+1)均為圖G的控制集,注意到其為兩兩不交的,從而d(G)≥r+1,矛盾。定理2證畢。

定理3 對(duì)于任意正整數(shù)m≥3和n≥2,均有d(Pm×Pn)=3

證明 令G=Pm×Pn,可見(jiàn)δ(G)=2,由引理1知d(G)≤3。

E下面只需將V(G)劃分為3個(gè)控制集V(G)=D1∪D2∪D3。

情況1 當(dāng)n≡0(m od3) 時(shí),令

情況2 當(dāng)n≡1(m od3) 時(shí),令V=V1∪V2,其中,V1中的點(diǎn)可以仿照情況1進(jìn)行劃分,我們只需對(duì)V2中的點(diǎn)進(jìn)行劃分即可。那么

情況3 當(dāng)n≡2(m od3) 時(shí),令V=V1∪V2,

綜上所述,V(G)能劃分為3個(gè)控制集,定理3證畢。

[1]BOND JA,MURTYV S R.Graph theory with applications[M].Amsterdam:Elsevier,1976:247-250.

[2]HAYNES T W,HEDETNIEMI S T,SLATER P J.Domination in graphs[M].New York:Marcel Dekker INC,1998:150-155.

[3] COCKAYNE E J,HEDETNIEMI S T.Towards a theory of domination in graphs[J].Networks,1977(7):247-261.

[4]ZELINKAB.Domatic number and linear arboricity of cacti[J].Slovaca Math,1986(36):41-54.

[5] ZELINKAB.Domatic number and degrees of vertices of a graph[J].Slovaca Math,1989(39):7-11.

[6]徐保根.圖的控制理論[M].北京:科學(xué)出版社,2008:103-113.

猜你喜歡
圖論乘積界限
界限
十幾歲(2022年21期)2022-11-19 11:14:42
間隙
乘積最大
基于FSM和圖論的繼電電路仿真算法研究
破次元
Dirichlet級(jí)數(shù)及其Dirichlet-Hadamard乘積的增長(zhǎng)性
構(gòu)造圖論模型解競(jìng)賽題
承諾是跨越時(shí)間界限的恒久
點(diǎn)亮兵書(shū)——《籌海圖編》《海防圖論》
孫子研究(2016年4期)2016-10-20 02:38:06
復(fù)變?nèi)呛瘮?shù)無(wú)窮乘積的若干應(yīng)用
深水埗区| 龙泉市| 温州市| 灵璧县| 和顺县| 哈巴河县| 新绛县| 慈利县| 花莲市| 公安县| 吐鲁番市| 宝应县| 枝江市| 罗江县| 周至县| 黄陵县| 连南| 威宁| 米易县| 竹山县| 杭锦后旗| 买车| 普宁市| 安溪县| 正镶白旗| 东丽区| 金阳县| 浙江省| 滦南县| 防城港市| 广昌县| 若羌县| 广东省| 阿拉善左旗| 察哈| 石城县| 绥江县| 叶城县| 富民县| 河池市| 南漳县|