圖的廣義燃燒數(shù)及其界值問題

劉佩佩,何志紅

(煙臺大學數(shù)學與信息科學學院,山東 煙臺 264005)

圖的燃燒最早由BONATO等[1]提出。在社交網(wǎng)絡中,一個人得到信息后,下一步會傳遞給他的朋友,而消息會隨著時間的推移而繼續(xù)傳播。信息傳播到整個網(wǎng)絡所需的最少時間問題可以轉化成圖論問題來解決,其本質是將信息在社會網(wǎng)絡中的傳播過程轉化成圖的燃燒過程。圖的燃燒是在簡單圖G的點集上定義的一個離散時間的圖過程,具體如下:在燃燒過程中,每個頂點要么被燃燒,要么未被燃燒;在初始時間t=0時,所有頂點未被燃燒;在時間t≥1時,每個時間選擇一個未被燃燒的頂點進行燃燒;一旦某個頂點在時間t被燃燒,則在時間t+1,它的所有鄰點都會自動被燃燒;如果一個頂點v被燃燒,則v保持燃燒狀態(tài)直到G的燃燒過程結束;當所有頂點全部被燃燒時,燃燒過程結束。G的燃燒數(shù)是指G的燃燒過程結束所需要的最少時間數(shù),記作b(G)。

然而,在現(xiàn)實生活中,當一個人只從一個渠道接收到某個信息時,他可能不會立即傳播,因為他不確定信息的真實性。而當他從幾個來源收到這個信息時,會增加對信息的識別,然后他才會將信息傳播給他的朋友。LI等[2]提出圖的廣義燃燒數(shù)來描述這一現(xiàn)象。圖的廣義燃燒是只有當頂點v在時間t有r個已燃燒的鄰點時,在時間t+1,v才會自動被燃燒,這里r≥1。G的廣義燃燒數(shù)記作br(G),它表示G的廣義燃燒過程結束所需要的最少時間數(shù)。例如,當n≥2,1≤r≤n-1時,br(Kn)=r+1。這個離散時間過程稱為圖G的r-燃燒過程。顯然,r=1時,br(G)=b(G)。通過定義可以得出r≤Δ(G),因為當r≥Δ(G)+1時,br(G)=|G|,這意味著G的任意頂點都不能通過r個鄰點被燃燒。

給定圖G和正整數(shù)r,其中r≤Δ(G),假設在G的廣義燃燒過程中,可以在k時間內燃燒整個圖G。對于任意i,其中1≤i≤k,將時間i時(第i時間)選擇的頂點記為xi,每個xi稱為一個火源。序列{x1,…,xk}稱為G的r-燃燒序,記為Br(G)。G的1-燃燒序也稱為G的燃燒序。顯然,G的廣義燃燒數(shù)等于G的所有r-燃燒序中最短的模。如果br(G)=k,則稱{x1,…,xk}是G的最佳r-燃燒序。

2014年以來,關于圖的燃燒數(shù)的研究越來越廣泛。BONATO等[1]確定了蜘蛛圖、完全二部圖、完全二叉樹等圖的燃燒數(shù),并給出圖的燃燒數(shù)的取值范圍。BESSY等[3]縮小了圖的燃燒數(shù)的上界,并給出二叉樹的燃燒數(shù)取到最大值的充要條件。文獻[4-8]計算了廣義Petersen圖、T無圈圖、theta圖、蜘蛛圖和路森林、飛機圖的燃燒數(shù)。文獻[9-10]討論了圖的積的燃燒數(shù),如字典積、笛卡爾積。LI等[2]提出廣義燃燒數(shù)的概念,并計算了n長路、n長圈、完全二部圖等圖的廣義燃燒數(shù),同時給出了廣義燃燒數(shù)的取值范圍,以及廣義燃燒數(shù)取到臨界值的充分必要條件。

本文計算了蝌蚪圖的廣義燃燒數(shù),并討論了廣義燃燒數(shù)在一定條件下的取值情況。

1 預備知識

本文考慮的圖均為簡單無向圖,概念和記號參考文獻[11]。

圖G=(V(G),E(G))是簡單無向圖,V(G)表示圖的點集,E(G)表示圖的邊集。設點v是G中任意一個頂點,v的鄰集是指v的所有鄰點構成的集合,記為NG(v),可簡記為N(v)。dG(v)表示v的在G中的鄰點個數(shù),dG(v)=|NG(v)|。設S是V(G)的任意一個子集,S的鄰集表示集合{v∈V(G)S|vu∈E(G),u∈S},記為NG(S),可簡記為N(S)。圖G中的兩點u和v之間的距離是指這兩點在G中最短路的長度,記為distG(u,v),可簡記為dist(u,v)。圖G中的一點u的離心率是max{dist(u,v):v∈V(G)}。直徑是指圖G的最大離心率,記為diam(G)。半徑是指圖G的最小離心率,記為rad(G)。如果點v到圖G的所有頂點的最大距離等于半徑,則稱v是G的中心。設S是V(G)的子集,如果點v?S,且點v與S中一點相鄰,則稱點v與S相鄰。設S是V(G)的子集,點v到S的距離是指v到S的所有點中的最短距離,記為distG(v,S),可簡記為dist(v,S)。如果圖H滿足V(H)?V(G),E(H)?E(G),則稱H是G的一個子圖。如果H是G的一個子圖,且V(H)=V(G),則稱H是G的生成子圖。如果H是G的一個子圖,且E(H)?{uv∈E(G)|u,v∈V(H)},則稱H是G的誘導子圖。如果H是G的一個子圖,H中任意頂點對(u,v),滿足distH(u,v)=distG(u,v),則稱H是G的等距離子圖。如果圖G中存在一條包含所有頂點的路P,則P稱為哈密爾頓路。

設G是簡單無向圖,v是G的任意一個頂點。給定一個正整數(shù)k,點v的k封閉鄰集表示集合{u∈V(G):dist(u,v)≤k},記作Nk[v]。N1[v]簡單記作N[v]。設{x1,…,xk}是圖G的一個燃燒序,其中k≥3,對于1≤i≤k,在第k步結束后,來自xi的火會燃燒所有到xi的距離小于k-i的頂點。另一方面,對任意v∈V(G),v要么是一個火源,要么在燃燒過程中通過至少一個火源被燃燒。換句話說,G中的任意頂點,如果不是一個火源,則必然存在i(1≤i≤k),使得該頂點是Nk-i[xi]中的一個元素。因此{x1,…,xk}是G的一個燃燒序當且僅當如下等式成立[1]:

Nk-1[x1]∪Nk-2[x2]∪…∪N0[xk]=V(G)。

(1)

以下是本文中用到的定理。

定理3[13]如果H是G的等距離子圖,則b(H)≤b(G)。

定理5[2]如果G是有n個點的連通圖,則對任意1≤r≤Δ(G),有br-1(G)≤br(G)。

定理6[2]如果G是有n個點的連通圖,則對任意1≤r≤Δ(G),有r+1≤br(G)≤n。

定理7[2]如果G是有n個點的連通圖,則br(G)=n當且僅當r=n-1。

2 主要結果

2.1 廣義燃燒數(shù)的界值問題

設G是連通圖,1≤r≤Δ(G),G的一個r-燃燒序為Br(G)={x1,…,xg},且G中存在點v使得v?Br(G)。如果在第t時間,點v未燃燒,但點v有r個已燃燒的鄰點y1,…,yr,顯然，在第t+1時間v會自動燃燒。為了便于研究,稱點v是在r-燃燒序Br(G)中被y1,…,yr引燃的點,t+1為引燃點v的時間。

定理8如果G是有n個頂點的連通圖,H是G的一個生成子圖,且1≤r≤Δ(G),則br(G)=br(H)。

證明設br(H)=k,{x1,…,xk}是H的一個r-燃燒序,易知{x1,…,xk}也是G的r-燃燒序,所以br(G)≤k。

定理9設G是有n個頂點的連通圖,V(G)={u1,…,un}。如果G的燃燒數(shù)br(G)=g,其中1≤r≤Δ(G),則存在最佳r-燃燒序Br(G)={x1,…,xg},使得x1,…,xr至少有一個公共鄰點。

證明當g=n時,由定理7,結論成立。當g≠n時,設G的一個最佳r-燃燒序為{x1,…,xg},此時V(G){x1,…,xg}≠?,即一定存在被引燃的點。如果x1,…,xr沒有公共鄰點,即在第r+1時間,沒有點被引燃,則可設在第t+1時間,第一次有點被引燃,這里t>r。將其中一個被引燃的點設為v,且v由{y1,…,yr}引燃。令{yr+1,…,yt}={x1,…,xt}{y1,…,yr},則{y1,…,yr,yr+1,…,yt,xt+1,…,xg}也是G的最佳r-燃燒序。

定理12設G是有n個頂點的連通圖,且1≤r≤Δ(G),Sk表示集合{v∈V(G)|d(v)

證明如果G中不存在點v使得d(v)=r-1,則有Sr=Sr-1,即br(G)=|Sr-1|。因為br-1(G)≥|Sr-1|,且由定理5可得,br-1(G)≤br(G)。所以有br-1(G)=br(G)。

2.2 蝌蚪圖的廣義燃燒數(shù)

設Cm是m個頂點的圈,Pn是n個頂點的路,蝌蚪圖G是指通過將Pn的起點與Cm中任意一點粘和起來構成的圖,顯然V(G)=V(Cm)∪V(Pn),且G有m+n-1個頂點。圖1為由C7和P5構成的蝌蚪圖。

圖1 由C7和P5構成的蝌蚪圖

定理13如果圖G是由Cm和Pn構成的蝌蚪圖,其中m≥3,n≥3,則一定存在正整數(shù)k≥2使得k2+k≤m+n<(k+1)2+(k+1)。

(1)r=1，若m+n=k2+k,則

br(G)=

若k2+k

br(G)=

(3)r=3，br(G)=m+n-2。

證明設V(Cm)={v1,…,vm},V(Pm)={u1,…,un},u1=v1。

(1)r=1。根據(jù)m+n的取值考慮以下兩種情況:

情況1m+n=k2+k。根據(jù)m的取值再分為以下四種情況。

情況1.12k-1≤m≤k2且m≠2k+1或k2-2。

設G1,G2分別是G的兩個誘導子圖,取V(G1)={v1,…,vk}∪{vm-k+2,…,vm}∪{u1,…,uk},V(G2)={vk+1,…,vm-k+1}∪{uk+1,…,un},顯然有V(G)=V(G1)∪V(G2)。因為|V(G2)|=(k-1)2且m≠2k+1或k2-2,所以G2可以劃分為P1，P3,…,P2(k-1)-1,其中Pi表示有i個頂點的路。取x1=v1,x1+i為P2(k-i)-1的中心,其中1≤i≤k-1。顯然{x1,…,xk}是G的一個r-燃燒序,即br(G)≤k。另一方面,由式(1)可知,G在k-1時間內最多燃燒1+3(k-2)+(k-2)2=k2-k-1個點,即br(G)≥k。因此br(G)=k。

情況1.2m=2k+1或k2-2。

令G1,G2是按情況1.1誘導的子圖,此時G2的兩個路分支分別為P2和P(k-1)2-2,無法劃分成P1，P3,…,P2(k-1)-1,由式(1)可得,br(G2)>k-1,且br(G)>k。當m=2k+1時,將G2劃分成P2,P2′,P5,P7,…,P2(k-1)-1,其中P2=vk+1vk+2,P2′=un-1un。取x1=v1,x1+i為P2(k-i)-1的中心,其中1≤i≤k-3,xk-1=vk+1,xk=un-1,xk+1=un,可得{x1,…,xk+1}是G的一個燃燒序。因此br(G)=k+1。

情況1.3m<2k+1。

情況1.4m>k2。

由定理2可得,br(Cm)>k。因為Cm是G的等距離子圖,所以br(G)>k。又由于m<(k+1)2,所以有br(Cm)=k+1。設Cm的一個r-燃燒序為{x1,…,xk+1},其中x1=v1,顯然{x1,…,xk+1}也是G的一個r-燃燒序,即br(G)=k+1。

情況2k2+k

因為G只有一個三度點,由式(1)可得,在k時間內,G最多燃燒1+3(k-1)+(k-1)2=k2+k-1個點,因此br(G)>k。設G′是由Cm′和Pn′構成的蝌蚪圖,V(Cm′)={v1,…,vm′},V(Pn′)={u1,…,un′},其中n′≥3,m′=m,m′+n′=(k+1)2+(k+1),顯然G是G′的等距離子圖,所以有br(G)≤br(G′)。根據(jù)m的取值分為以下四種情況。

情況2.12k+1≤m≤(k+1)2且m≠2k+3或(k+1)2-2。

由情況1.1可得,br(G′)=k+1,所以br(G)≤k+1。又因為br(G)>k,故有br(G)=k+1。

情況2.2m=2k+3或(k+1)2-2。

設G1′,G2′分別是G′-un′的兩個誘導子圖,取V(G1′)={v1,…,vk+1}∪{vm-k+1,…,vm}∪{u1,…,uk+1},V(G2′)={vk+2,…,vm-k}∪{uk+2,…,un′-1}。當m=2k+3時,因為|V(G2′)|=k2-1,所以G2′可以劃分為P1,P2,P5,P7,…,P2k-1,其中P2=vk+2vk+3,P1=un′-1。取x1=v1,x1+i為P2(k+1-i)-1的中心,xk=vk+2,xk+1=un′-1,其中1≤i≤k-2,得到G′-un′的一個r-燃燒序{x1,…,xk+1},所以br(G′-un′)≤k+1。因為G是G′-un′的等距離子圖,所以br(G)≤k+1。同理,當m=(k+1)2-2時,br(G)≤k+1。于是有br(G)=k+1。

情況2.3m=2k+3。

情況2.4m>(k+1)2。

由定理2可得,br(Cm)>k+1,所以有br(G)>k+1。由情況1.4可得,br(G′)=k+2,故有br(G)≤k+2。綜上得br(G)=k+2。

(3)r=3。因為G只有一個三度點,所以br(G)≥m+n-2。又因為{v2,…,vm,u2,…,un}是G的一個r-燃燒序,所以有br(G)≤m+n-2。于是br(G)=m+n-2。

3 總 結

本文計算了蝌蚪圖的廣義燃燒數(shù),并討論了廣義燃燒數(shù)的幾個界值問題。廣義燃燒數(shù)還有許多內容值得研究,例如:路與圈的其他組合圖的廣義燃燒數(shù);對于不同的r,廣義燃燒數(shù)之間的關系;廣義燃燒數(shù)在社會網(wǎng)絡中的實際應用等。