图的积的广义燃烧数

刘佩佩 何志红

摘 要：图的燃烧数是指在图的燃烧过程中所需要的最少时间数。2021年，李银奎等人提出图的广义燃烧数。图G的广义燃烧数br（G）是指图的广义燃烧过程需要的最少时间数。本文解决了完全k叉树的广义燃烧数的一般性结果，并部分解决了字典积和笛卡尔积的广义燃烧数问题。

关键词：燃烧数;广义燃烧数;完全k叉树;字典积;笛卡尔积;强积

中图分类号：O157.5  文献标识码：A  文章编号：1673-260X（2022）01-0001-04

1 引言

图的燃烧最早由BONATO等人[1]提出。在社交网络中，一个人得到信息后，下一步会传递给他的朋友，而消息会随着时间的推移而继续传播。如果要考虑信息传播到整个网络所需的最少时间，那么可以转化成图论问题来解决，也就是将信息在社会网络中的传播过程转化成图的燃烧过程。图的燃烧是在简单图G的点集上定义的一个离散时间的图过程。具体如下：在燃烧过程中，每个顶点要么被燃烧，要么未被燃烧。在初始时间t=0时，所有顶点未被燃烧。在时间t≥1时，每个时间选择一个未被燃烧的顶点进行燃烧。一旦某个顶点在时间t被燃烧，则在时间t+1，它的所有邻点都会自动被燃烧。如果一个顶点v被燃烧，则v保持燃烧状态直到G的燃烧过程结束。当所有顶点全部被燃烧时，燃烧过程结束。G的燃烧数记作b（G），它表示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-1燃燒序。

近几年，关于图的燃烧数的研究持续不断。BONATO等[1]确定了蜘蛛图、完全二部图、完全二叉树等图的燃烧数，并给出图的燃烧数的取值范围。BESSY等[3]缩小了图的燃烧数的上界，并给出二叉树的燃烧数取到最大值的充要条件。SIM等计算了广义Petersen图、T无圈图、theta图[4-8]等图的燃烧数。DIETER等讨论了图的积的燃烧数，如字典积、笛卡尔积[9，10]。LI等[2]提出广义燃烧数的概念，并计算了n长路，n长圈，完全二部图等图的广义燃烧数，同时给出了广义燃烧数的取值范围，以及广义燃烧数取到临界值的充分必要条件。

本文计算了完全k叉树的广义燃烧数，并给出图的笛卡尔积、强积、字典积的广义燃烧数的取值范围。

2 预备知识

本文中考虑的图均为简单无向图，概念和记号参考[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中所有顶点对的最大距离称为直径，记为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的一个子图，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）相邻当且仅当u1u2∈E（G）或u1=u2且v1v2∈E（H）。图H和图H的笛卡尔积记作G×H，它的顶点集为V（G×H）=V（G）×V（H）。两个顶点（u1，v1）和（u2，v2）相邻当且仅当要么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）相邻当且仅当u1u2∈E（G）或v1v2∈E（H）。通过定义，可以得到G×H？哿G·H？哿G？茚H。

3 主要结果

3.1 完全k叉树的广义燃烧数

无圈连通图称为树，树上度为1的点称为叶子。设s是树T的任意一个顶点，若令s为T的根，则称T为以s为根的根树。根树中的顶点也称节点，T中任意节点的深度为该点到s的距离。根树T的深度是T中所有点的深度的最大值。如果T中存在路P=v1，…，vl，其中v1=s，则称vi为vi-1的子代，其中1<i≤l。二叉树是一个根树，它的每个节点都有两个子代。完全二叉树是所有叶子都有相同深度的二叉树。类似二叉树的概念，k叉树表示每个节点都有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）。

证明 设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时间全部燃烧。因此，当rad（H）=1时，br（G？茚H）≤r+2。当rad（H）≥2时，设点v是H的中心。因为燃烧完（u1，v）…，（ur，v）后，最多再需要rad（H）时间，G？茚H全部被燃烧，所以br（G？茚H）≤r+rad（H）。

4 总结及展望

本文计算了完全k叉树的广义燃烧数，并给出图的笛卡尔积、强积、字典积的广义燃烧数的取值范围。广义燃烧图还有许多内容值得探索，例如：对于不同的r，广义燃烧数之间的关系;广义燃烧数在社会网络中的实际应用等。期待在未来对广义燃烧数有更广泛的研究。

参考文献：

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