圖的積的廣義燃燒數(shù)

劉佩佩 何志紅

摘 要：圖的燃燒數(shù)是指在圖的燃燒過(guò)程中所需要的最少時(shí)間數(shù)。2021年，李銀奎等人提出圖的廣義燃燒數(shù)。圖G的廣義燃燒數(shù)br（G）是指圖的廣義燃燒過(guò)程需要的最少時(shí)間數(shù)。本文解決了完全k叉樹(shù)的廣義燃燒數(shù)的一般性結(jié)果，并部分解決了字典積和笛卡爾積的廣義燃燒數(shù)問(wèn)題。

關(guān)鍵詞：燃燒數(shù);廣義燃燒數(shù);完全k叉樹(shù);字典積;笛卡爾積;強(qiáng)積

中圖分類號(hào)：O157.5 ?文獻(xiàn)標(biāo)識(shí)碼：A ?文章編號(hào)：1673-260X（2022）01-0001-04

1 引言

圖的燃燒最早由BONATO等人[1]提出。在社交網(wǎng)絡(luò)中，一個(gè)人得到信息后，下一步會(huì)傳遞給他的朋友，而消息會(huì)隨著時(shí)間的推移而繼續(xù)傳播。如果要考慮信息傳播到整個(gè)網(wǎng)絡(luò)所需的最少時(shí)間，那么可以轉(zhuǎn)化成圖論問(wèn)題來(lái)解決，也就是將信息在社會(huì)網(wǎng)絡(luò)中的傳播過(guò)程轉(zhuǎn)化成圖的燃燒過(guò)程。圖的燃燒是在簡(jiǎn)單圖G的點(diǎn)集上定義的一個(gè)離散時(shí)間的圖過(guò)程。具體如下：在燃燒過(guò)程中，每個(gè)頂點(diǎn)要么被燃燒，要么未被燃燒。在初始時(shí)間t=0時(shí)，所有頂點(diǎn)未被燃燒。在時(shí)間t≥1時(shí)，每個(gè)時(shí)間選擇一個(gè)未被燃燒的頂點(diǎn)進(jìn)行燃燒。一旦某個(gè)頂點(diǎn)在時(shí)間t被燃燒，則在時(shí)間t+1，它的所有鄰點(diǎn)都會(huì)自動(dòng)被燃燒。如果一個(gè)頂點(diǎn)v被燃燒，則v保持燃燒狀態(tài)直到G的燃燒過(guò)程結(jié)束。當(dāng)所有頂點(diǎn)全部被燃燒時(shí)，燃燒過(guò)程結(jié)束。G的燃燒數(shù)記作b（G），它表示G的燃燒過(guò)程結(jié)束所需要的最少時(shí)間數(shù)。

然而，在現(xiàn)實(shí)生活中，當(dāng)一個(gè)人只從一個(gè)渠道接收到某個(gè)信息時(shí)，他可能不會(huì)立即傳播，因?yàn)樗淮_定信息的真實(shí)性。但當(dāng)他從幾個(gè)來(lái)源收到這個(gè)信息時(shí)，會(huì)增加對(duì)信息的識(shí)別，然后他才會(huì)將信息傳播給他的朋友。LI等人[2]提出圖的廣義燃燒數(shù)來(lái)描述這一現(xiàn)象。圖的廣義燃燒是只有當(dāng)頂點(diǎn)v在時(shí)間t有r個(gè)已燃燒的鄰點(diǎn)時(shí)，在時(shí)間t+1，v才會(huì)自動(dòng)被燃燒，這里r≥1。G的廣義燃燒數(shù)記作br（G），它表示G的廣義燃燒過(guò)程結(jié)束所需要的最少時(shí)間數(shù)。例如，當(dāng)n≥2，1≤r≤n-1時(shí)，br（Kn）=r+1。這個(gè)離散時(shí)間過(guò)程稱為圖G的r-燃燒過(guò)程。顯然，r=1時(shí)，br（G）=b（G）。通過(guò)定義可以得出r≤？駐（G），因?yàn)楫?dāng)r≥？駐（G）+1時(shí)，br（G）=|G|，這意味著G的任意頂點(diǎn)都不能通過(guò)r個(gè)鄰點(diǎn)被燃燒。

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

近幾年，關(guān)于圖的燃燒數(shù)的研究持續(xù)不斷。BONATO等[1]確定了蜘蛛圖、完全二部圖、完全二叉樹(shù)等圖的燃燒數(shù)，并給出圖的燃燒數(shù)的取值范圍。BESSY等[3]縮小了圖的燃燒數(shù)的上界，并給出二叉樹(shù)的燃燒數(shù)取到最大值的充要條件。SIM等計(jì)算了廣義Petersen圖、T無(wú)圈圖、theta圖[4-8]等圖的燃燒數(shù)。DIETER等討論了圖的積的燃燒數(shù)，如字典積、笛卡爾積[9，10]。LI等[2]提出廣義燃燒數(shù)的概念，并計(jì)算了n長(zhǎng)路，n長(zhǎng)圈，完全二部圖等圖的廣義燃燒數(shù)，同時(shí)給出了廣義燃燒數(shù)的取值范圍，以及廣義燃燒數(shù)取到臨界值的充分必要條件。

本文計(jì)算了完全k叉樹(shù)的廣義燃燒數(shù)，并給出圖的笛卡爾積、強(qiáng)積、字典積的廣義燃燒數(shù)的取值范圍。

2 預(yù)備知識(shí)

本文中考慮的圖均為簡(jiǎn)單無(wú)向圖，概念和記號(hào)參考[11]。

圖G=（V（G），E（G））是簡(jiǎn)單無(wú)向圖，V（G）表示圖的點(diǎn)集，E（G）表示圖的邊集。設(shè)點(diǎn)v是G中任意一個(gè)頂點(diǎn)，v的鄰集是指v的所有鄰點(diǎn)構(gòu)成的集合，記為NG（v），可簡(jiǎn)記為N（v）。dG（v）表示v的在G中的鄰點(diǎn)個(gè)數(shù)，dG（v）=|NG（v）|。設(shè)S是V（G）的任意一個(gè)子集，S的鄰集表示集合{v∈V（G）＼S|vu∈E（G），u∈S}，記為NG（S），可簡(jiǎn)記為N（S）。圖G中的兩點(diǎn)u和v之間的距離是指這兩點(diǎn)在G中最短路的長(zhǎng)度，記為distG（u，v），可簡(jiǎn)記為dist（u，v）。圖G中所有頂點(diǎn)對(duì)的最大距離稱為直徑，記為diam（G）。圖G中所有頂點(diǎn)對(duì)的最小距離稱為半徑，記為rad（G）。如果點(diǎn)v到圖G的所有頂點(diǎn)的最大距離等于半徑，則稱v是G的中心。設(shè)S是V（G）的子集，如果點(diǎn)v？埸S，且點(diǎn)v與S中一點(diǎn)相鄰，則稱點(diǎn)v與S相鄰。設(shè)S是V（G）的子集，點(diǎn)v到S的距離是指v到S的所有點(diǎn)中的最短距離，記為distG（v，S），可簡(jiǎn)記為dist（v，S）。如果圖H滿足V（H）？哿V（G），E（H）？哿E（G），則稱H是G的一個(gè)子圖。如果H是G的一個(gè)子圖，H中任意頂點(diǎn)對(duì)（u，v），滿足distH（u，v）=distG（u，v），則稱H是G的等距離子圖。

圖G和圖H的字典積記作G·H，它的頂點(diǎn)集為V（G·H）=V（G）×V（H）。兩個(gè)頂點(diǎn)（u1，v1）和（u2，v2）相鄰當(dāng)且僅當(dāng)u1u2∈E（G）或u1=u2且v1v2∈E（H）。圖H和圖H的笛卡爾積記作G×H，它的頂點(diǎn)集為V（G×H）=V（G）×V（H）。兩個(gè)頂點(diǎn)（u1，v1）和（u2，v2）相鄰當(dāng)且僅當(dāng)要么v1=v2且u1u2∈E（G），要么u1=u2且v1v2∈E（H）。圖G和圖H的強(qiáng)積記作G？茚H，它的頂點(diǎn)集為V（G？茚H）=V（G）×V（H）。兩個(gè)頂點(diǎn)（u1，v1）和（u2，v2）相鄰當(dāng)且僅當(dāng)u1u2∈E（G）或v1v2∈E（H）。通過(guò)定義，可以得到G×H？哿G·H？哿G？茚H。

3 主要結(jié)果

3.1 完全k叉樹(shù)的廣義燃燒數(shù)

無(wú)圈連通圖稱為樹(shù)，樹(shù)上度為1的點(diǎn)稱為葉子。設(shè)s是樹(shù)T的任意一個(gè)頂點(diǎn)，若令s為T(mén)的根，則稱T為以s為根的根樹(shù)。根樹(shù)中的頂點(diǎn)也稱節(jié)點(diǎn)，T中任意節(jié)點(diǎn)的深度為該點(diǎn)到s的距離。根樹(shù)T的深度是T中所有點(diǎn)的深度的最大值。如果T中存在路P=v1，…，vl，其中v1=s，則稱vi為vi-1的子代，其中1<i≤l。二叉樹(shù)是一個(gè)根樹(shù)，它的每個(gè)節(jié)點(diǎn)都有兩個(gè)子代。完全二叉樹(shù)是所有葉子都有相同深度的二叉樹(shù)。類似二叉樹(shù)的概念，k叉樹(shù)表示每個(gè)節(jié)點(diǎn)都有k個(gè)子代的根樹(shù)，記為T(mén)k。完全k叉樹(shù)是所有葉子都有相同深度的k叉樹(shù)。

定理9 如果G和H都是連通圖，其中V（G）=n，V（H）=m，且1≤r≤min{m，n}如果rad（H）=1，則 ?br（G？茚H）≤r+2，如果rad（H）≥2，則br（G？茚H）≤r+rad（H）。

證明 設(shè)V（G）={u1，…，un}，V（H）={v1，…，vm}。 V（G？茚H）的一個(gè)劃分為V（G？茚H）=S1∪…∪Sm，其中Si={（u，vi）|u∈V（G）}，1≤i≤m。易知，如果vivj∈E（H），則在G？茚H中，Si和Sj完全相鄰，其中1≤i，j≤m。即如果vivj∈E（H），且在第t時(shí)間，Si中有r個(gè)點(diǎn)被燃燒，則在第t+1時(shí)間，Sj全部被燃燒，Si中剩余頂點(diǎn)在t+2時(shí)間全部燃燒。因此，當(dāng)rad（H）=1時(shí)，br（G？茚H）≤r+2。當(dāng)rad（H）≥2時(shí)，設(shè)點(diǎn)v是H的中心。因?yàn)槿紵辏╱1，v）…，（ur，v）后，最多再需要rad（H）時(shí)間，G？茚H全部被燃燒，所以br（G？茚H）≤r+rad（H）。

4 總結(jié)及展望

本文計(jì)算了完全k叉樹(shù)的廣義燃燒數(shù)，并給出圖的笛卡爾積、強(qiáng)積、字典積的廣義燃燒數(shù)的取值范圍。廣義燃燒圖還有許多內(nèi)容值得探索，例如：對(duì)于不同的r，廣義燃燒數(shù)之間的關(guān)系;廣義燃燒數(shù)在社會(huì)網(wǎng)絡(luò)中的實(shí)際應(yīng)用等。期待在未來(lái)對(duì)廣義燃燒數(shù)有更廣泛的研究。

參考文獻(xiàn)：

〔1〕BONATO A， JANSSEN J， ROSHANBIN E. Burning a Graph as a Model of Social Contagion[J]. Springer International Publishing， 2014：13-22.

〔2〕LI Y， QIN X， LI W. The generalized burning number of graphs[J]. Applied Mathematics and Computation， 2021， 411： 126306.

〔3〕BESSY S， BONATO A， JANSSEN J， et al. Bounds on the burning number[J]. Discrete Applied Mathematics， 2018， 235： 16-22.

〔4〕SIM K A， TAN T S， WONG K B. On the burning number of generalized petersen graphs[J]. Bulletin of the Malaysian Mathematical Sciences Society， 2018， 41（03）： 1657-1670.

〔5〕ZHANG R， YU Y， LIU H. Burning numbers of t-unicyclic graphs[J]. arXiv preprint arXiv：2103.07840， 2021.

〔6〕HL A， RZ A， XH B. Burning number of theta graphs[J]. Applied Mathematics and Computation， 2019， 361：246-257.

〔7〕BONATO A， LIDBETTER T. Bounds on the burning numbers of spiders and path-forests[J]. Theoretical Computer Science，2019， 794：12-19.

〔8〕BONATO A， GUNDERSON K， Shaw A. Burning the plane： densities of the infinite Cartesian grid[J]. 2020， 36： 1311-1335.

〔9〕DIETER M， PAWE P， ELHAM R. Burning number of graph products[J]. Theoretical Computer Science， 2018， 746： 124-135.

〔10〕JYOTHSNA B， RADHAKRISHNAN N B. Burning Number of some Families and some Products of Graphs[J]. Indian Journal of Pure and Applied Mathematics， 2018， 118（18）：1489.

〔11〕BONDY J A， MURTY U S R. Graph theory with applications[M]. London： Macmillan， 1976.

〔12〕ROSHANBIN E. Burning a graph as a model for the spread of social contagion[J]. Dalhousie University， Halifax， Nova Scotia， 2016.

〔13〕ROSHANBIN E， BONATO A， JANSSEN J. How to Burn a Graph[J]. Internet Mathematics， 2016， 12（1-2）： 85-100.