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

劉佩佩 何志紅

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

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

中圖分類號：O157.5 ?文獻標識碼：A ?文章編號：1673-260X（2022）01-0001-04

1 引言

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

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

對于給定的圖G和正整數(shù)r，其中r≤？駐（G）。假設(shè)在G的廣義燃燒過程中，可以在k時間內(nèi)燃燒整個圖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-1燃燒序。

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

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

2 預(yù)備知識

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

圖G=（V（G），E（G））是簡單無向圖，V（G）表示圖的點集，E（G）表示圖的邊集。設(shè)點v是G中任意一個頂點，v的鄰集是指v的所有鄰點構(gòu)成的集合，記為NG（v），可簡記為N（v）。dG（v）表示v的在G中的鄰點個數(shù)，dG（v）=|NG（v）|。設(shè)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中所有頂點對的最大距離稱為直徑，記為diam（G）。圖G中所有頂點對的最小距離稱為半徑，記為rad（G）。如果點v到圖G的所有頂點的最大距離等于半徑，則稱v是G的中心。設(shè)S是V（G）的子集，如果點v？埸S，且點v與S中一點相鄰，則稱點v與S相鄰。設(shè)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的一個子圖，H中任意頂點對（u，v），滿足distH（u，v）=distG（u，v），則稱H是G的等距離子圖。

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

3 主要結(jié)果

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

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

定理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）的一個劃分為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時間，Si中有r個點被燃燒，則在第t+1時間，Sj全部被燃燒，Si中剩余頂點在t+2時間全部燃燒。因此，當(dāng)rad（H）=1時，br（G？茚H）≤r+2。當(dāng)rad（H）≥2時，設(shè)點v是H的中心。因為燃燒完（u1，v）…，（ur，v）后，最多再需要rad（H）時間，G？茚H全部被燃燒，所以br（G？茚H）≤r+rad（H）。

4 總結(jié)及展望

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

參考文獻：

〔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.