图的强均匀点荫度

Strong Equitable Vertex Arboricity of Graphs

摘要: 图G的均匀k-划分是将图G的顶点划分，使得每个划分类导出的子图是一个森林且任意两个划分类中的顶点数最多相差1。图G的强均匀点荫度是最小整数k，使得对任意的$k^{\prime }\ge k$ ，图G都有一个均匀$k^{\prime }$ -划分。本文证明每个无割点的外平面图G，它的强均匀点荫度至多为，继而证明了无割点的外平面图满足猜想：对任何平面图G，强均匀点荫度至多是。同时，得到平方图的强均匀点荫度的下界为$\lceil \frac{\Delta +1}{2}\rceil$ ，证明圈$C_n$ 的平方图在$n=5$ 时，强均匀点荫度为3，当$n\ne 5$ 时，强均匀点荫度为2，从而证明圈的平方图满足强均匀点荫的猜想。

Abstract: An equitable k-partition of a graph G is a partition of the vertex set of G such that the subgraph induced by each partition class is a forest and the sizes of any two parts differ by at most one. The strong equitable vertex arboricity of G is the minimum integer k so that G has an equitably $k^{\prime }$ - partitioned for an $k^{\prime }\ge k$ . This paper proves that the strong equitable vertex arboricity of each outerplanar has no cut-vertices G is at most 2, and then proves that the outerplanar satisfies the conjecture that for any plan G, the strong equitable vertex arboricity is at most 3. Meanwhile, the lower bound of the strong equitable vertex arboricity of the square graph is $\lceil \frac{\Delta +1}{2}\rceil$ , which proved that the square graph of the circuits $C_n$ is 3 when $n=5$ , and the strong equitable vertex arboricity is 2 when $n\ne 5$ , so that the square graph of the circuits satisfies the conjecture of strong equitable vertex arboricity.

1. 引言

本文所涉及的图都是简单、有限的无向图，使用$V\left(G\right),E\left(G\right)$ 分别表示图G的顶点集和边集。其它未标明的记号都来自[1]。对任意的点$v\in V\left(G\right)$ ，$d_G\left(V\right)$ 表示图G中点v的度，即图G中与点v相关联的边数。如果$d_G\left(v\right)=k$ ，那么就称点v是一个k度点。k-度点是指度为k的点，1-度点也被称为叶子。$N_G\left(v\right)$ 表示图G中与点v的相邻的顶点集合，$N_G\left(v\right)$ 中的每个点都称为v的邻点。对于图G中任意两点$u,v$ ，它们之间的距离为连接这两个点的最短路的长度，用$d_G\left(u,v\right)$ 表示。

图G的均匀k-划分是将图G的顶点划分为$V_1,V_2,\cdots ,V_K$ ，使得每个划分类导出的子图是一个森林，且任意两个划分类中的顶点数最多相差一个。图G具有均匀k-划分的最小整数k称为图G的均匀点荫度，用符号$a_{eq}\left(G\right)$ 表示。图G的强均匀点荫度是最小整数k，使得对任意的$k^{\prime }\ge k$ ，图G都有一个均匀k'-划分，用符号$a_{eq}^{*}\left(G\right)$ 表示。显然，对任意的图G，都有$a_{eq}\left(G\right)\le a_{eq}^{*}\left(G\right)$ ，而且$a_{eq}\left(G\right)$ 与$a_{eq}^{*}\left(G\right)$ 的差值可以很大。例如[2]，完全二部图$K_{n,n}$ ，$a_{eq}\left(K_{n,n}\right)=2$ ，当是t奇数，$2n=t\left(t+3\right)$ 时，$a_{eq}^{*}\left(K_{n,n}\right)=2\lfloor \frac{\sqrt{8n+9}-1}{4}\rfloor$ 。

图的均匀点荫度是吴建良、张欣[2]等人基于Fan和Kierstead [3]等人对放松均匀染色的基础上提出的，吴建良和张欣等人证明了每个围长至少是5的平面图强均匀点荫度最多是3，每个围长至少是6的平面图和外平面图的强均匀点荫度最多是2。同时他们还提出了两个猜想。

猜想1 对任何一个图G，$a_{eq}^{*}\left(G\right)\le \lceil \frac{\Delta \left(G\right)+1}{2}\rceil$ 。

猜想2 对每个平面图G，存在一个常数c，使得$a_{eq}^{*}\left(G\right)\le c$ 。

猜想1 (强均匀点荫度猜想)已经被证明对每个$\Delta \left(G\right)\ge \frac{\left|G\right|}{2}$ 的图[4]，亚立方体图[5]，5-退化图[6]，$\Delta \left(G\right)\ge 9.818d$ 的d-退化图[7]成立。由于每个平面图都是5-退化图，所以陈冠涛[6]等人证明了对于每个平面图猜想1都成立。Esperet和Lemoine [8]证明了如果一个图G有无圈k-染色，$k\ge 2$ ，则G能被均匀划分为$k-1$ 个导出森林。由于任意一个平面图有无圈5-染色[9]，所以他们证明了对每个平面图$a_{eq}^{*}\le 4$ 。即猜想1被Esperet和Lemoine彻底解决了。Chartrand和Kronk [10]证明每个平面图的点荫度至多为3，所以张欣等人[11]提出：

猜想3 每个平面图G，$a_{eq}^{*}\left(G\right)\le 3$ 。

2015年，张欣[12]证明了对任意两个圈长至多是4的点不交的平面图以及围长至少是4且没有两个相邻4-圈的平面图的强均匀点荫度至多是3。随后刘维婵和张欣[11]证明了外1-平面图的强均匀点荫度至多是3。

下面我们给出外平面图和平方图的相关定义及其性质。

对一个图，如果它的某个面包含某个点，则称这个面与这个点相关联。对一个图，它的所有顶点都与同一个面相关联，则这个图称为外平面图。用符号$f=\left[u_1,u_2,\cdots ,u_n\right]$ 表示外平面图的面，其中$u_1,u_2,\cdots ,u_n$ 是f的以循环次序被遍历一次的所有顶点。图G的平方图$G^2$ 是以$V\left(G\right)$ 为顶点集，任意两点$u,v$ 在图$G^2$ 中相邻当且仅当$1\le d_G\left(u,v\right)\le 2$ 。

1996年，吴建良[13]证明了无割点的外平面图。

引理1 [13]. 设G是一个无割点的外平面图，且$\left|V\left(G\right)\right|\ge 3$ ，则至少有下列情况之一：

(1) 存在两个相邻的2-度点$u,v$ ；

(2) 存在一个2-度点u和一个3-度点v相邻，$N_G\left(u\right)=\left\{v,w\right\}$ ，并使得$vw\in E\left(G\right)$ ；

(3) 存在一个2-度点u相邻于两个4-度点v和w，使得$vw\in E\left(G\right)$ ；

(4) 存在两个不相邻的2-度点u和v共邻于一个4-度点w，$N_G\left(w\right)=\left\{u,v,x,y\right\}$ ，且使得$ux,vy,xy\in E\left(G\right)$ 。

2. 主要定理

定理1. 如果图G是一个无割点的连通的外平面图，那么$a_{eq}^{*}\left(G\right)\le 2$ 。

定理2. 图G是一个简单图，设它的最大度为$\text{Δ}$ ，则$a_{eq}^{*}\left(G^2\right)\ge \lceil \frac{\text{Δ}+1}{2}\rceil$ 。

定理3. 圈$C_n\left(n\ge 3\right)$ 的平方图的强均匀点荫度

$a_{eq}^{*}\left(C_n^2\right)=\{\begin{array}{l}3n=5;\\ 2其它.\end{array}$

3. 定理1的证明

证明. 当$V\left(G\right)=1$ 时，图G是由一个孤立点v构成的图，则$a_{eq}^{*}\left(G\right)=1$ 。

当$V\left(G\right)=2$ 时，图G是由一条边$e=uv$ 构成，则$a_{eq}^{*}\left(G\right)=1$ 。

当$V\left(G\right)\ge 3$ 时，假设$a_{eq}^{*}\left(G\right)\ge 3$ ，且$\left|E\left(G\right)\right|+\left|V\left(G\right)\right|$ 尽可能小。

由引理1，当G中存在两个相邻的2-度点$u,v$ 时，由G的极小性知，$V\left(G\right)-\left\{u,v\right\}$ 能被均匀2-划分为$V_1,V_2$ 。因为$\left|V_i\cap N_G\left(u\right)\right|\le 1$ ，$\left|V_i\cap N_G\left(v\right)\right|\le 1$ ，$i\in \left\{1,2\right\}$ ，所以将u移到$V_1$ 中，v移到$V_2$ 中，则图G中存在2-划分${V^{\prime }}_1=V_1\cup u$ ，${V^{\prime }}_2=V_2\cup v$ ，$G\left[{V^{\prime }}_i\right]$ 是森林。因为$\Vert V_1\Vert -\Vert V_2\Vert \le 1$ ，所以$\Vert {V^{\prime }}_1\Vert -\Vert {V^{\prime }}_2\Vert \le 1$ 。由强均匀点荫度的定义知，$a_{eq}^{*}\left(G\right)\le 2$ ，与$a_{eq}^{*}\left(G\right)\ge 3$ 矛盾，所以假设不成立。

当G中有情况(2)时，则图G中存在两点$u,v$ ，$d_G\left(u\right)=2$ ，$d_G\left(v\right)=3$ 。由G的极小性知，$V\left(G\right)-\left\{u,v\right\}$ 能被均匀2-划分为$V_1,V_2$ 。因$d_G\left(v\right)=3$ ，所以$V\left(G\right)-\left\{u,v\right\}$ 中存在一个划分类$V_i$ ，$i\in \left\{1,2\right\}$ ，使得$\left|V_i\cap N_G\left(v\right)\right|=1$ 或$\left|V_i\cap N_G\left(v\right)\right|=2$ ，不妨设$V_i=V_1$ 。将u移到$V_1$ 中，v移到$V_2$ 中，则图G中存在2-划分${V^{\prime }}_1=V_1\cup u$ ，${V^{\prime }}_2=V_2\cup v$ 。因为$\Vert V_1\Vert -\Vert V_2\Vert \le 1$ ，所以$\Vert {V^{\prime }}_1\Vert -\Vert {V^{\prime }}_2\Vert \le 1$ 。又因为$\left|V_1\cap N_G\left(u\right)\right|\le 1$ ，$\left|V_2\cap N_G\left(v\right)\right|\le 1$ ，所以$G\left[{V^{\prime }}_i\right]$ 是森林，$i\in \left\{1,2\right\}$ 。由强均匀点荫度的定义知，$a_{eq}^{*}\left(G\right)\le 2$ ，与$a_{eq}^{*}\left(G\right)\ge 3$ 矛盾，所以假设不成立。

当G中有情况(3)或(4)时，则图G中存在两点$u,w$ ，$d_G\left(u\right)=2$ ，$d_G\left(w\right)=4$ 。由G的极小性知，$V\left(G\right)-\left\{u,w\right\}$ 能被均匀2-划分为$V_1,V_2$ 。因为$d_G\left(w\right)=4$ ，所以$V\left(G\right)-\left\{u,w\right\}$ 中存在一个划分类$V_i$ ，$i\in \left\{1,2\right\}$ ，使得$\left|V_i\cap N_G\left(w\right)\right|=2$ 或$\left|V_i\cap N_G\left(w\right)\right|=3$ ，不妨设$V_i=V_1$ 。将u移到$V_1$ 中，w移到$V_2$ 中，则图G中存在2-划分${V^{\prime }}_1=V_1\cup u$ ，${V^{\prime }}_2=V_2\cup w$ 。因为$\Vert V_1\Vert -\Vert V_2\Vert \le 1$ ，所以$\Vert {V^{\prime }}_1\Vert -\Vert {V^{\prime }}_2\Vert \le 1$ 。又因为$\left|V_1\cap N_G\left(u\right)\right|\le 1$ ，$\left|V_2\cap N_G\left(w\right)\right|\le 1$ ，所以$G\left[{V^{\prime }}_i\right]$ 是森林，$i\in \left\{1,2\right\}$ 。由强均匀点荫度的定义知，$a_{eq}^{*}\left(G\right)\le 2$ ，与$a_{eq}^{*}\left(G\right)\ge 3$ 矛盾，所以假设不成立。

综上所述，当图G是一个无割点的外平面图时，则$a_{eq}^{*}\left(G\right)\le 2$ 。 □

4. 定理2和定理3的证明

证明定理2. 设$v\in V\left(G\right)$ ，$d_G\left(v\right)=\text{Δ}$ 。由平方图的定义知，在$G^2$ 中点v及其与v相邻的点构成一个完全图$K_{\text{Δ}+1}$ 。因为完全图中任意三点构成一个三圈，所以$K_{\text{Δ}+1}$ 在每个划分类中的顶点数至多为2。所以$a_{eq}^{*}\left(K_{\text{Δ}+1}\right)=\lceil \frac{\text{Δ}+1}{2}\rceil$ 。因为$K_{\text{Δ}+1}$ 是$G^2$ 子图，所以$a_{eq}^{*}\left(G^2\right)\ge a_{eq}^{*}\left(K_{\text{Δ}+1}\right)$ ，即$a_{eq}^{*}\left(G^2\right)\ge \lceil \frac{\text{Δ}+1}{2}\rceil$ 。

证明定理3. 当$n=3$ 时，$C_3^2=K_3$ ，则$a_{eq}^{*}\left(C_3^2\right)=2$ 。

当$n=4$ 时，$C_4^2=K_4$ ，则$a_{eq}^{*}\left(C_4^2\right)=2$ 。

当$n=5$ 时，$C_5^2=K_5$ ，则$a_{eq}^{*}\left(C_5^2\right)=3$ 。

当$n\ge 6$ 时，设$V\left(C\right)=\left\{x_1,x_2,\cdots ,x_n\right\}$ ，$G=C_n^2$ 。用正整数$\left\{1,2,\cdots ,k\right\}$ 表示颜色，设f一个从$V\left(C\right)$ 到$\left\{1,2,\cdots ,k\right\}$ 映射，$V_i=\left\{v|f\left(v\right)=i\right\}$ ，$1\le i\le k$ 。

若$n\equiv 0\left(\mathrm{mod}4\right)$ ，那么选定以$x_1$ 为起点进行下列染色：$f\left(x_1\right)=f\left(x_2\right)=1$ ，$f\left(x_3\right)=f\left(x_4\right)=2$ ，$f\left(x_5\right)=f\left(x_6\right)=1$ ，$f\left(x_7\right)=f\left(x_8\right)=2$ ，$\cdots$ ，$f\left(x_{n-3}\right)=f\left(x_{n-2}\right)=1$ ，$f\left(x_{n-1}\right)=f\left(x_n\right)=2$ 。如此染色之后，得到$\left|V_1\right|=\left|V_2\right|=n/2$ ，$V_1,V_2$ 中都是$d_{C_n}\left(x_a,x_b\right)=1$ 的两点构成的边，$a\ne b$ ，$a,b\in \left\{1,2,\cdots ,n\right\}$ ，且这些边在$V_i$ 中都是相互独立的，所以$G\left[V_i\right]$ 是森林，$i\in \left\{1,2\right\}$ ，则G有均匀2-划分。

若$n\equiv 1\left(\mathrm{mod}4\right)$ ，那么选定以$x_1$ 为起点进行下列染色：$f\left(x_1\right)=f\left(x_2\right)=1$ ，$f\left(x_3\right)=f\left(x_4\right)=2$ ，$f\left(x_5\right)=f\left(x_6\right)=1$ ，$f\left(x_7\right)=f\left(x_8\right)=2$ ，$\cdots$ ，$f\left(x_{n-4}\right)=f\left(x_{n-3}\right)=1$ ，$f\left(x_{n-2}\right)=2$ ，$f\left(x_{n-1}\right)=1$ ，$f\left(x_n\right)=2$ 。如此染色之后，得到$\left|V_1\right|=\frac{n-3}{2}+1=\frac{n-1}{2}$ ，$\left|V_2\right|=\frac{n-3}{2}+2=\frac{n+1}{2}$ ，$V_1,V_2$ 中的边都是相互独立，所以$\Vert V_1\Vert -\Vert V_2\Vert =1$ ，$G\left[V_i\right]$ 是森林，$i\in \left\{1,2\right\}$ ，则G有均匀2-划分。

若$n\equiv 2\left(\mathrm{mod}4\right)$ ，那么选定以$x_1$ 为起点进行下列染色：$f\left(x_1\right)=f\left(x_2\right)=1$ ，$f\left(x_3\right)=f\left(x_4\right)=2$ ，$f\left(x_5\right)=f\left(x_6\right)=1$ ，$f\left(x_7\right)=f\left(x_8\right)=2$ ，$\cdots$ ，$f\left(x_{n-3}\right)=f\left(x_{n-2}\right)=2$ ，$f\left(x_{n-1}\right)=1$ ，$f\left(x_n\right)=2$ 。得到$\left|V_1\right|=\left|V_2\right|=\frac{n}{2}$ ，$G\left[V_i\right]$ 是森林，$i\in \left\{1,2\right\}$ ，则G有均匀2-划分。

若$n\equiv 3\left(\mathrm{mod}4\right)$ ，那么选定以$x_1$ 为起点进行下列染色：$f\left(x_1\right)=f\left(x_2\right)=1$ ，$f\left(x_3\right)=f\left(x_4\right)=2$ ，$f\left(x_5\right)=f\left(x_6\right)=1$ ，$f\left(x_7\right)=f\left(x_8\right)=2$ ，$\cdots$ ，$f\left(x_{n-2}\right)=f\left(x_{n-1}\right)=1$ ，$f\left(x_n\right)=2$ 。得到$\left|V_1\right|=\frac{n-3}{2}+2=\frac{n+1}{2}$ ，$\left|V_2\right|=\frac{n-3}{2}+1=\frac{n-1}{2}$ ，$V_1,V_2$ 中的边都是相互独立，所以$\Vert V_1\Vert -\Vert V_2\Vert =1$ ，$G\left[V_i\right]$ 是森林，则G有均匀2-划分。

因为$G=C_n^2$ ，所以G中没有均匀1-划分。对任意大于2的整数k，以$x_1$ 为起点依次用颜色$\left\{1,2,\cdots ,k\right\}$ 进行染色，得到每个类中都是孤立点或孤立点和一条边，所以$G\left[V_i\right]$ 是森林，$\left|V_i\right|=\lceil \frac{n}{k}\rceil$ 或$\left|V_i\right|=\lfloor \frac{n}{k}\rfloor$ ，$i,j\in \left\{1,2,\cdots ,k\right\}$ ，即$\Vert V_i\Vert -\Vert V_j\Vert \le 1$ 。综上，对任意大于2的整数k，G都有一个均匀k-划分。

综上所述，当$n\ge 6$ 时，圈$C_n\left(n\ge 3\right)$ 的平方图的强均匀点荫度$a_{eq}^{*}\left(C_n^2\right)=2$ 。 □

5. 结语

均匀点荫度虽然是 2013年提出来的，但是人们对它的研究才刚刚开始，而且猜想1，即均匀点荫度猜想还没有被完全证明，猜想3也只是证明了对一些特殊图结论成立。我们对无割点的外平面图和圈的平方图的强均匀点荫度进行讨论，丰富了此领域在外平面图和平方图上的研究成果。

NOTES

^*通讯作者。