非星型树有标号打包进其六次幂

《Discrete Mathematics》:Labeled packing of a non-star tree into its sixth power

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

编辑推荐:

   摘要 2013年,Duchêne等人[3]提出了一种图打包问题的新变体,称为图的标签打包。本文介绍了一些关于非星树到其六次幂的标签打包的结果。首先,我们证明了路径 $P_n$($n \geq 4$)存在一个具有 $\lceil n/4 \rceil$ 个标签的标签打包到 $

  

摘要

2013年,Duchêne等人[3]提出了一种图打包问题的新变体,称为图的标签打包。本文介绍了一些关于非星树到其六次幂的标签打包的结果。首先,我们证明了路径 $P_n$($n \geq 4$)存在一个具有 $\lceil n/4 \rceil$ 个标签的标签打包到 $P_n^4$ 中。我们还证明了非星树 $T$ 可以找到一个具有 $m_T + \lceil (n - m_T)/5 \rceil$ 个标签的标签打包到 $T^6$ 中,其中 $n$ 是 $T$ 的顶点数,$m_T$ 表示从 $T$ 中最多可以移除的叶子节点数量,使得所得的树仍然是一个非星树。

引言

本文考虑的所有图都是有限图。对于图 $G$,$V(G)$ 和 $E(G)$ 分别表示其顶点集和边集。对于 $V(G)$ 中的任意两个顶点 $x$ 和 $y$,$x$ 与 $y$ 之间的边记为 $xy$。我们用 $n$ 和 $e$ 分别表示 $V(G)$ 和 $E(G)$ 的基数。我们用 $N_G(x)$ 表示图 $G$ 中顶点 $x$ 的邻居集合。图 $G$ 中顶点 $x$ 的度数 $d_G(x)$ 是集合 $N_G(x)$ 的基数。为简便起见,我们用 $d(x)$ 代替 $d_G(x)$,用 $N(x)$ 代替 $N_G(x)$。$G$ 中两个顶点 $x$ 和 $y$ 之间的距离记为 $d_G(x, y)$,为简便起见通常用 $d(x, y)$。当且仅当 $V(H) \subseteq V(G)$ 且 $E(H) \subseteq E(G)$ 时,我们说图 $H$ 是 $G$ 的子图。设 $H$ 是 $G$ 的一个子图,如果 $E(G)$ 中所有顶点都在 $V(H)$ 中的边也都是 $E(H)$ 中的边,则称 $H$ 是 $G$ 的诱导子图。对于 $U \subseteq V(G)$,我们用 $G - U$ 表示从 $G$ 中删除 $U$ 中所有顶点及其关联边后得到的图。对于 $F \subseteq E(G)$,我们定义 $G - F$ 为从 $G$ 中移除 $F$ 中所有边后得到的图。如果 $G$ 中任意两个顶点都可以通过一条路径相连,则称图 $G$ 是连通的。图 $G$ 的连通分量是关于 $\subseteq$ 的最大诱导连通子图。我们用 $C_G(x)$ 表示 $G$ 中包含 $x$ 的连通分量。

设 $k \geq 2$ 为整数。我们用 $G^k$ 表示 $G$ 的 $k$ 次幂,它是从 $G$ 出发,每当 $xy \notin E(G)$ 且 $d(x, y) \leq k$ 时添加边 $xy$ 后得到的图。树中度数为1的顶点称为叶子。可以很容易地注意到,从非星树中移除一组叶子节点后,结果可能是一个非星树,也可能是一个星树。对于非星树 $T$,我们用 $m_T$ 表示从 $T$ 中最多可以移除的叶子节点数,使得所得的图仍然是一个非星树。我们用 $P_n$ 表示阶为 $n$ 的路径,我们说一条路径是 $xy$-路径,如果 $x$ 和 $y$ 是它的两个端点。设 $P = v_1v_2 \ldots v_n$ 为一条路径,如果 $P_1, P_2, \ldots, P_k$($k \geq 2$)是 $P$ 中两两顶点不相交的子路径,使得 $V(P) = \bigcup_{i=1}^k V(P_i)$,$P_i$ 是 $x_iy_i$-路径,其中 $x_1 = v_1$,$y_k = v_n$,且 $y_ix_{i+1} \in E(P)$ 对 $i = 1, 2, \ldots, k-1$ 成立,则我们记 $P = P_1P_2 \ldots P_k$。

图打包的概念最早由 Bollobás 和 Eldridge [1] 以及 Sauer 和 Spencer [7] 在20世纪70年代末各自独立提出,其定义如下:设 $G$ 是阶为 $n$ 的图,$\sigma$ 是从 $V(G)$ 到 $V(K_n)$ 的一个排列。由 $\sigma$ 诱导的映射 $\sigma^*: E(G) \to E(K_n)$ 满足 $\sigma^*(xy) = \sigma(x)\sigma(y)$。如果存在 $k$ 个排列 $\sigma_i: V(G) \to V(K_n)$($i = 1, \ldots, k$),使得当 $i \neq j$ 时 $\sigma_i^*(E(G)) \cap \sigma_j^*(E(G)) = \emptyset$,则称 $G$ 在完全图 $K_n$ 中有一个 $k$ 个副本的打包。这样的打包称为 $G$ 的一个 $k$-放置。因此,$\sigma: V(G) \to V(K_n)$ 是 $G$ 的一个2-放置(或嵌入),如果每当边 $xy$ 属于 $E(G)$ 时,$\sigma(x)\sigma(y)$ 不属于 $E(G)$;即如果 $G$ 有一个2-放置,则 $G$ 是其补图的一个子图。$V(G)$ 上的一个排列 $\sigma$ 满足对所有 $V(G)$ 中的 $x$ 都有 $\sigma(x) \neq x$,则称为无不动点排列。

在图及其补图中打包路径和树的问题一直是组合数学中长期存在的基本研究课题,在现有文献中得到了广泛探索。关于这一领域的综述,我们参考 Wo?niak [11] 和 Yap [13] 的综述文章。在文献[2]中,给出了所有阶为 $n$ 且边数 $e = n - 2$ 的图存在2-放置的完整描述。文献[4]中提供了关于阶为 $n$ 且边数 $e = n$ 的图的类似结果。关于非星树,众所周知任何非星树都包含在其自身的补图中。这一结果在许多方面得到了改进,特别是在考虑关于嵌入的一些附加信息和条件时。这样的结果的一个例子是文献[12]中作为引理包含的以下定理:

**定理 1.1** 设 $T$ 是阶为 $n > 3$ 的非星树。则存在 $T$ 的一个2-放置 $\sigma$,使得对所有 $x \in V(T)$,有 $d(x, \sigma(x)) \leq 3$。

该定理直接推出以下推论:

**推论 1.2** 设 $T$ 是阶为 $n > 3$ 的非星树。则存在 $T$ 的一个嵌入 $\sigma$,使得 $\sigma(T) \subset T^7$。

在文献[5]中,Kheddouci等人通过以下定理给出了更好的改进:

**定理 1.3** 设 $T$ 是一个非星树,$x$ 是 $T$ 的一个顶点。则存在 $V(T)$ 上的一个排列 $\sigma$ 满足以下四个条件:
1. $\sigma$ 是 $T$ 的一个2-放置。
2. $\sigma(T) \subseteq T^4$。
3. $d(x, \sigma(x)) = 1$。
4. 对 $x$ 的每个邻居 $y$,$d(y, \sigma(y)) \leq 2$。

标签图打包问题是图论中一个著名的研究领域,已经得到了相当多的研究。它由 Duchêne 等人在文献[3]中引入:

**定义 1** 考虑一个有 $n$ 个顶点的图 $G$。设 $f$ 是从 $V(G)$ 到集合 $\{1, 2, \ldots, p\}$ 的映射,其中 $p \in \mathbb{N}$。如果存在 $k$ 个排列 $\sigma_i: V(G) \to V(K_n)$($i = 1, \ldots, k$)满足:
1. 对所有 $i \neq j$,$\sigma_i^*(E(G)) \cap \sigma_j^*(E(G)) = \emptyset$。
2. 对 $G$ 的每个顶点 $v$,有 $f(v) = f(\sigma_1(v)) = f(\sigma_2(v)) = \ldots = f(\sigma_k(v))$。

则映射 $f$ 称为 $G$ 的 $k$ 个副本到 $K_n$ 中的一个 $p$-标签打包。$G$ 能实现 $G$ 的 $k$ 个副本的 $p$-标签打包的最大正整数 $p$ 称为 $G$ 的标签 $k$-打包数,记为 $\lambda_k(G)$。

Duchêne 等人还研究了图的两个副本的标签打包,并证明了文献[3]中作为引理呈现的以下结果:

**定理 1.4** 设 $G$ 是一个有 $n$ 个顶点的图,$I$ 是 $G$ 的一个最大独立集。如果存在 $G$ 到 $K_n$ 的嵌入,则 $\lambda_2(G) \leq |I| + \lfloor (n - |I|)/2 \rfloor$。

此外,Tahraoui 等人在文献[9]中给出了当 $G$ 是竹节虫树或路径时 $\lambda_2(G)$ 的精确值,以及非星树 $T$ 的 $\lambda_2(T)$ 的一个下界。2017年,Tahraoui 等人在文献[8]中改进了 Wo?niak 在文献[10]中提出的界,并证明了以下结果:

**定理 1.5** 设 $G$ 是一个阶为 $n \geq 2$ 且 $e \leq n - 2$ 的图。则 $\lambda_2(G) \geq \lfloor 2n/3 \rfloor$。

在本文中,我们研究寻找 $G$ 到 $G^k$ 的 $p$-标签打包,这个新问题的定义如下:

**定义 2** 设 $f$ 是从 $V(G)$ 到集合 $\{1, 2, \ldots, p\}$ 的映射,其中 $p \in \mathbb{N}$。如果存在一个排列 $\sigma: V(G) \to V(K_n)$ 满足:
1. $\sigma$ 是 $G$ 的一个2-放置。
2. $\sigma(G) \subseteq G^k$。
3. 对 $G$ 的每个顶点 $v$,有 $f(v) = f(\sigma(v))$。

则映射 $f$ 称为 $G$ 到 $G^k$ 中的一个 $p$-标签打包。$G$ 能实现 $G$ 到 $G^k$ 的 $p$-标签打包的最大正整数 $p$ 称为标签打包 $k$-次幂数,记为 $w_k(G)$。

在这个框架下的一个结果来自 Mortada 等人在文献[6]中证明的结论:存在一个非星树 $T$ 到其 $k$ 次幂 $T^k$($k \geq 5$)的具有 $m_T + 1$ 个标签的标签打包。

我们从寻找 $P_n$ 到 $P_n^4$ 的 $p$-标签打包开始研究,并在第2.1节中证明了以下定理:

**定理 1.6** 设 $u$ 和 $v$ 是路径 $P_n$ 的端点,其中 $n \geq 4$。则存在 $V(P_n)$ 上的一个排列 $\sigma$ 满足以下条件:
1. $\sigma$ 是一个2-放置。
2. $\sigma(P_n) \subseteq P_n^4$。
3. $d(u, \sigma(u)) = 1$ 且 $d(v, \sigma(v)) \leq 1$。
4. $\sigma$ 的每个环的长度最多为4。

上述结果使我们能够证明以下内容:

**推论 1.7** 对于路径 $P_n$(其中 $n \geq 4$),$w_4(P_n) \geq \lceil n/4 \rceil$。

然后,在第2.2节中,我们将研究扩展到非星树。我们首先通过一种特定类型的排列,从非星树 $T$ 到 $T^6$ 的标签打包入手:

**定义 3** 设 $T$ 是一个非星树,$x$ 是 $T$ 的一个顶点。则 $V(T)$ 上的一个无不动点排列 $\sigma$ 如果满足以下条件,则称为 $(T, x)$-良好2-放置:
1. $\sigma$ 是 $T$ 的一个2-放置。
2. $\sigma(T) \subseteq T^6$。
3. $d(x, \sigma(x)) \leq 2$。
4. 对 $x$ 的每个邻居 $y$,$d(y, \sigma(y)) \leq 3$。
5. 对每个叶子 $y$,$d(y, \sigma(y)) \leq 4$。
6. 对 $T$ 的每个顶点 $y$,$d(y, \sigma(y)) \leq 5$。
7. $\sigma$ 的每个环的长度最多为5。

然后我们证明以下主要结果:

**定理 1.8** 设 $T$ 是一个非星树,$x$ 是 $T$ 的一个顶点。则存在一个 $(T, x)$-良好2-放置。

上述结果使我们能够很容易地找到 $w_6(T)$ 的一个下界,我们将证明:

**推论 1.9** 对每个有 $n$ 个顶点的非星树 $T$,$w_6(T) \geq m_T + \lceil (n - m_T)/5 \rceil$。

分节摘要

$P_n$ 到 $P_n^4$ 的标签打包

本节的目标是证明定理1.6。

**定理 1.6 的证明**

我们通过归纳法进行。对于每条路径 $P_n$($4 \leq n \leq 7$),我们将在下面引入 $V(P_n)$ 上的一个排列 $\sigma$,满足命题中的条件。

对于 $P_4 = x_1x_2x_3x_4$,$\sigma = (x_1x_2x_4x_3)$。

对于 $P_5 = x_1x_2x_3x_4x_5$,$\sigma = (x_1x_2x_5x_4)(x_3)$。

对于 $P_6 = x_1x_2x_3x_4x_5x_6$,$\sigma = (x_1x_2x_5x_4)(x_3)(x_6)$。

对于 $P_7 = x_1x_2x_3x_4x_5x_6x_7$,$\sigma = (x_1x_2x_5)(x_3x_7x_6)(x_4)$。

假设 $n \geq 8$ 且定理对所有 $n' < n$ 成立。则 $P_n$ 可以被划分为两个子路径 $P'$ 和 $P''$,使得 $l(P') \geq 3$ 且 $l(P'') \geq 3$。

特殊树的良好2-放置

设 $T$ 是图1中的树,$k \geq 2$。

我们将为每个 $v \in \{x, y, \alpha_1, \beta_1\}$ 定义一个 $(T, v)$-良好2-放置 $\sigma$。

设 $r, r' \in \mathbb{N} \cup \{0\}$:

如果 $k = 2r$,$m = 2r'$,$r \geq 1$ 且 $r' \geq 1$,则设 $\sigma' = (\alpha_1x\beta_2)(\beta_1y\alpha_2)$。考虑:
$$\sigma = \begin{cases} \sigma' & \text{如果 } r=1 \text{ 且 } r'=1, \\ \sigma' \prod_{i=2}^{i=r} (\alpha_{2i-1}\alpha_{2i}) & \text{如果 } r>1 \text{ 且 } r'=1, \\ \sigma' \prod_{i=2}^{i=r'} (\beta_{2i-1}\beta_{2i}) & \text{如果 } r=1 \text{ 且 } r'>1, \\ \sigma' \prod_{i=2}^{i=r} (\alpha_{2i-1}\alpha_{2i}) \prod_{i=2}^{i=r'} (\beta_{2i-1}\beta_{2i}) & \text{如果 } r>1 \text{ 且 } r'>1. \end{cases}$$

如果 $k = 2r+1$,$m = 2r'$,$r > 0$ 且 $r' \geq 1$,则设 $\sigma' = (x\alpha_1y\beta_1\beta_2)$。考虑:
$$\sigma = \begin{cases} \sigma' \prod_{i=1}^{i=r} (\alpha_{2i}\alpha_{2i+1}) & \text{如果 } r>0 \text{ 且 } r'=1, \\ \sigma' \prod_{i=1}^{i=r} (\alpha_{2i}\alpha_{2i+1}) \prod_{i=2}^{i=r'} (\beta_{2i-1}\beta_{2i}) & \text{如果 } r>0 \text{ 且 } r'>1. \end{cases}$$

CRediT 作者贡献声明

所有作者对本工作做出了均等的贡献。

Sara Nasser | Maidoun Mortada | Hamamache Kheddouci
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

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

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号