具有指定燃烧数的极值树

《Discrete Applied Mathematics》:Extremal trees with prescribed burning numbers

【字体: 大 中 小 】 时间:2026年09月27日 来源:Discrete Applied Mathematics 1.1

编辑推荐:

   # 允许序列及其诱导的极值树 ## 摘要 图燃烧问题源于社会影响的传播,而燃烧数衡量传播速度。一个自然的问题是刻画在给定燃烧数下按阶取极值的图。由于连通图的燃烧数可由其某棵生成树达到,因此极值树的研究为该问题提供了洞见。据此,我们专注于在给定燃烧数下识别此类极值树(在图同

  

# 允许序列及其诱导的极值树

## 摘要

图燃烧问题源于社会影响的传播,而燃烧数衡量传播速度。一个自然的问题是刻画在给定燃烧数下按阶取极值的图。由于连通图的燃烧数可由其某棵生成树达到,因此极值树的研究为该问题提供了洞见。据此,我们专注于在给定燃烧数下识别此类极值树(在图同胚意义下)。在本文中,我们在同胚不可约树上引入允许序列的概念,并建立了一个通用框架。我们随后确定了某个允许序列是否诱导出一棵具有指定燃烧数的极值树。此外,我们获得了一些关于极值 $n$-蛛(spider)在给定燃烧数下所能达到的最小直径的结果。

## 引言

Bonato 等人 [4] 提出了图燃烧问题以衡量社会影响在社交网络中的传播速度。图燃烧问题旨在最小化将所有顶点"点燃"所需的步数,这是一个离散的确定性过程。在燃烧过程中,每个顶点处于两种状态之一:已燃或未燃。在初始轮次 $t=0$ 时,所有顶点均未燃。对于后续每一轮 $t \geq 1$,若一个未燃顶点与某个已燃顶点相邻,则其状态自动变为已燃;否则,它可以被选为本轮唯一可被点燃的候选顶点。一旦顶点变为已燃,该状态在燃烧的剩余过程中保持不变。过程持续至无未燃顶点,此时我们称该图已被燃尽。

设图 $G$ 在 $m$ 轮内被燃尽。令 $x_i$ 表示第 $i$ 轮中被选为燃烧的顶点,其中 $1 \leq i \leq m$。我们将序列 $(x_1, x_2, \ldots, x_m)$ 定义为图 $G$ 的燃烧序列,其中每个 $x_i$ 称为一个燃烧源。$G$ 的燃烧数定义为使 $G$ 的所有顶点都被燃尽所需的最少轮数,记为 $b(G)$。若图 $G$ 能在至多 $m$ 轮内被完全燃尽(即 $b(G) \leq m$),则称 $G$ 是 $m$-可燃的。

许多图的家族的燃烧数已被广泛研究。Bonato 等人 [4] 证明了 $n$ 个顶点的路径和环的燃烧数为 $\lceil \frac{n}{2} \rceil$,并提出如下猜想:

**燃烧数猜想 [4]** 若 $G$ 是连通图,则 $b(G) \leq \sqrt{|V(G)|}$。

此外,Bonato 等人 [4] 表明连通图的燃烧数等于其所有生成树中燃烧数的最小值。因此,只需验证树上的燃烧数猜想即可。

虽然对一般树而言该猜想仍未解决,但已在特定图的家族中得到验证,例如 $\theta$ 图 [22]、$t$-单环图 [31]、循环图 [10]、网格图和区间图 [12]、齿轮图和日图 [30]、广义彼得森图 [27]、毛毛虫 [14]、[20],以及路径森林 [6]、[8]、[21]。至于蛛(spider),Bonato 和 Lidbetter [6] 以及 Das 等人 [8] 各自独立证明了这些简单树满足燃烧数猜想。后来,Tan 和 Teh [28] 表明蛛的阶可以轻易超过 $m^2$,同时保证 $m$-可燃性,并建立了紧的上界。他们还在 [29] 中研究了双蛛和路径森林的可燃性。最近,Devroye 等人 [9] 表明随机树的燃烧数上界显著更小,量级为 $n^{1/3}$。

图燃烧问题的 NP 完全性已在若干图类中建立,包括蛛、路径森林、一般图 [2] 和定向树 [15]。同时,燃烧数的一般改进上界也是研究热点。最初,对于阶为 $n$ 的任意连通图 $G$,Bessy 等人 [3] 建立了上界 $b(G) \leq \frac{1}{2}\sqrt[7]{n} + 3$。该上界随后由 Land 和 Lu [18] 改进为 $\frac{-3+\sqrt[7]{24n+3}}{4}$。Bastide 等人 [1] 最近获得了改进的上界 $\frac{8+\sqrt[12]{n+64}}{3}$。几乎同时,Norin 和 Turcotte [26] 做出了卓越贡献,证明了燃烧数猜想在渐近意义下成立,即 $b(G) \leq (1+o(1))\sqrt{n}$。同时,Murakami [25] 表明燃烧数猜想对于不含二度顶点的树类成立。

除了关注图燃烧问题和燃烧数猜想之外,一些研究者还对燃烧数的变体进行了研究。$k$-燃烧问题最初由 [24] 研究。该变体允许每轮选择 $k$ 个顶点,而经典燃烧中 $k=1$。后来,$k$-燃烧问题在蛛和置换图 [11] 上被证明为 NP 完全。此外,$k$-慢燃烧问题(限制每个燃烧顶点每轮能点燃的邻居数量的变体)的上界和近似算法已被研究 [13]。此外,图燃烧还从参数化复杂性 [16]、[17] 和随机性 [23] 的角度进行了研究。图燃烧的近似算法也在 [5] 中被提出。2023 年,燃烧数的有向变体被研究,给定一个无向图,目标是将它转化为有向图以使燃烧过程延长 [7]。

在本文中,给定一个预定的燃烧数,我们通过引入允许序列来识别具有最大可达阶的相应极值树。在第 2 节中,我们首先介绍一些术语,然后给出图燃烧的一些一般性质,以及对我们先前工作中关于具有指定燃烧数的极大树的轻微推广。在下一节中,我们解释了同胚不可约树上的允许序列的概念。我们证明了具有指定燃烧数且在其同胚类中阶最大的任何树都由某些允许序列诱导(见定理 3.13),并且由具有相同特征的允许序列诱导的树具有相同的阶(见引理 3.7)。因此,在合适的允许序列之间进行比较是识别极值树的有效方法。在下一节中,我们说明了该框架(涉及允许序列及第 3 节的结果)如何适用于识别具有四个分支顶点的极值树。最后,我们研究了当 $n$-蛛需要具有指定燃烧数且其阶在所有具有相同燃烧数的 $n$-蛛中最大时,所能达到的最小直径。

## 第 2 节 预备知识

在本文中,我们只考虑简单、有限、无向图。设 $G$ 为这样一个图。$G$ 中顶点 $u$ 和 $v$ 之间的距离,记为 $d(u,v)$,是连接 $u$ 和 $v$ 的最短路径的长度。$G$ 的直径为 $\text{diam}(G) = \max\{d(u,v) \mid u,v \in V(G)\}$。与顶点 $v$ 相连的边数称为 $v$ 的度数。

设 $(x_1, x_2, x_3, \ldots, x_m)$ 是图 $G$ 的长为 $m$ 的燃烧序列。若 $b(G) = m$,则称其为最优燃烧序列。来自 $x_i$ 的火焰传播,在 $m$ 轮内……

## 第 3 节 允许序列及其诱导的极值树

本节专注于通过允许序列来确定具有指定燃烧数的树的最大阶。对于同胚不可约树 $T$,$T$-允许序列部分编码了由 $T$ 的分支顶点诱导的子树的结构信息,包括这些分支顶点的相对位置。该框架使得燃烧源的选择更为精确,并为分析燃烧序列提供了系统方法。

## 第 4 节 案例研究:四个分支顶点

由定理 3.13(第 2a 部分),若树 $T'$ 在以下意义下是极值的——即在同胚且燃烧数相同的树中 $T'$ 的阶最大——则 $T'$ 由某个 $T$-允许序列诱导,其中 $T$ 是与 $T'$ 同胚的同胚不可约树。因此,通过比较对应的规范 $T$-允许序列来识别具有燃烧数 $m$ 的此类树 $T'$ 将是一个好策略。由定理 3.13,其中一些序列可以从我们的考虑中排除。

## 第 5 节 关于最小直径的结果

若一个图是连通的,其燃烧数由 $r+1$ 上界约束,其中 $r$ 是图的半径。这在考虑以图的中心为初始燃烧源的燃烧序列时显然是成立的。在本节中,我们研究极值 $n$-蛛在给定燃烧数下所能达到的最小直径。(提醒一下,极值意味着该 $n$-蛛在燃烧数相同的 $n$-蛛中阶最大。)

**引理 5.1** 设 $T$ 是一个 $n$-蛛……

## 利益冲突声明

代表所有作者,通讯作者声明不存在利益冲突。

## 致谢

第一作者和通讯作者感谢马来西亚理科大学授予 Wen Chean Teh 的研究大学资助(项目编号:1001/PMATHS/8011129)的财政支持。本工作是我们已发表在 [19] 中的工作的延续。据我们所知,本文的框架和结果确实是全新的。感谢匿名审稿人,本文是预印本 arXiv:2504.20427v2 的改进修订版。

Eugene Jun Tong Leong | Kai An Sim | Wen Chean Teh
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号