刘佩佩,何志红
(烟台大学数学与信息科学学院,山东 烟台 264005)
图的燃烧最早由BONATO等[1]提出。在社交网络中,一个人得到信息后,下一步会传递给他的朋友,而消息会随着时间的推移而继续传播。信息传播到整个网络所需的最少时间问题可以转化成图论问题来解决,其本质是将信息在社会网络中的传播过程转化成图的燃烧过程。图的燃烧是在简单图G的点集上定义的一个离散时间的图过程,具体如下:在燃烧过程中,每个顶点要么被燃烧,要么未被燃烧;在初始时间t=0时,所有顶点未被燃烧;在时间t≥1时,每个时间选择一个未被燃烧的顶点进行燃烧;一旦某个顶点在时间t被燃烧,则在时间t+1,它的所有邻点都会自动被燃烧;如果一个顶点v被燃烧,则v保持燃烧状态直到G的燃烧过程结束;当所有顶点全部被燃烧时,燃烧过程结束。G的燃烧数是指G的燃烧过程结束所需要的最少时间数,记作b(G)。
然而,在现实生活中,当一个人只从一个渠道接收到某个信息时,他可能不会立即传播,因为他不确定信息的真实性。而当他从几个来源收到这个信息时,会增加对信息的识别,然后他才会将信息传播给他的朋友。LI等[2]提出图的广义燃烧数来描述这一现象。图的广义燃烧是只有当顶点v在时间t有r个已燃烧的邻点时,在时间t+1,v才会自动被燃烧,这里r≥1。G的广义燃烧数记作br(G),它表示G的广义燃烧过程结束所需要的最少时间数。例如,当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和正整数r,其中r≤Δ(G),假设在G的广义燃烧过程中,可以在k时间内燃烧整个图G。对于任意i,其中1≤i≤k,将时间i时(第i时间)选择的顶点记为xi,每个xi称为一个火源。序列{x1,…,xk}称为G的r-燃烧序,记为Br(G)。G的1-燃烧序也称为G的燃烧序。显然,G的广义燃烧数等于G的所有r-燃烧序中最短的模。如果br(G)=k,则称{x1,…,xk}是G的最佳r-燃烧序。
2014年以来,关于图的燃烧数的研究越来越广泛。BONATO等[1]确定了蜘蛛图、完全二部图、完全二叉树等图的燃烧数,并给出图的燃烧数的取值范围。BESSY等[3]缩小了图的燃烧数的上界,并给出二叉树的燃烧数取到最大值的充要条件。文献[4-8]计算了广义Petersen图、T无圈图、theta图、蜘蛛图和路森林、飞机图的燃烧数。文献[9-10]讨论了图的积的燃烧数,如字典积、笛卡尔积。LI等[2]提出广义燃烧数的概念,并计算了n长路、n长圈、完全二部图等图的广义燃烧数,同时给出了广义燃烧数的取值范围,以及广义燃烧数取到临界值的充分必要条件。
本文计算了蝌蚪图的广义燃烧数,并讨论了广义燃烧数在一定条件下的取值情况。
本文考虑的图均为简单无向图,概念和记号参考文献[11]。
图G=(V(G),E(G))是简单无向图,V(G)表示图的点集,E(G)表示图的边集。设点v是G中任意一个顶点,v的邻集是指v的所有邻点构成的集合,记为NG(v),可简记为N(v)。dG(v)表示v的在G中的邻点个数,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的任意一个顶点。给定一个正整数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.1 广义燃烧数的界值问题
设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的燃烧数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)。 设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,则一定存在正整数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。根据m+n的取值考虑以下两种情况: 情况1m+n=k2+k。根据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′)。根据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。 本文计算了蝌蚪图的广义燃烧数,并讨论了广义燃烧数的几个界值问题。广义燃烧数还有许多内容值得研究,例如:路与圈的其他组合图的广义燃烧数;对于不同的r,广义燃烧数之间的关系;广义燃烧数在社会网络中的实际应用等。2.2 蝌蚪图的广义燃烧数
