笛卡尔积图的f-点稳定数

The f-Vertex Stability Number of Cartesian Product Graphs

摘要: 图的不变量点稳定数是最近的热点问题之一，它被应用于设计算法解决图论的某些特定问题。设$f$ 是图不变量，图$G$ 的$f$ -点稳定数$v{s}_f\left(G\right)$ 定义为使得$f\left(G-V^{\prime }\right)\ne f\left(G\right)$ 成立的最小点子集$V^{\prime }$ 的基数。在本文中，通过不变量$f$ 的性质，讨论笛卡尔积图的$f$ -点稳定数的界。

Abstract: The invariant vertex stability number of graph is one of the recent hot topics, which is applied to design algorithms to solve certain problems in graph theory. Let $f$ be an invariant of graphs, and the $f$ -vertex stability number $v{s}_f\left(G\right)$ of a graph $G$ is defined as the cardinality of the minimum vertex subset $V^{\prime }$ such that $f\left(G-V^{\prime }\right)\ne f\left(G\right)$ . In this paper, we discuss the bounds of the $f$ -vertex stability number for Cartesian product graphs through the properties of the invariant $f$ .

1. 引言

本文考虑有限简单图$G=\left(V,E\right)$ ，同时假设图不变量f是一个非负实函数。图不变量是指图在同构条件下仍然保持不变的一种性质，它往往和图的自身结构和特征有关，不依赖于图的某一种表示。研究图不变量不仅可以让我们深刻理解图的结构特性，还能借此设计算法用于解决图论当中各种各样的问题。文献[1]-[4]中发现对给定图的不变量稳定数，可以通过删除点，删除边，增加点以及增加边的方式进行改变。Haynes [3]等人通过对图G进行删点，删边和加边的方式考虑不变量是否改变，给出了最大度$\Delta \left(G\right)$ ，最小度$\delta \left(G\right)$ ，独立数$\alpha \left(G\right)$ 等不变量的一般性结论。Bauer [4]等人给出了使得图的独立数增加或减少的条件，同时对图的f-边稳定数$e{s}_f\left(G\right)$ 进行了定义，即在图G中能找到一个最小的边集$E^{\prime }$ 使得$f\left(G-E^{\prime }\right)\ne f\left(G\right)$ ，则有$e{s}_f\left(G\right)=\left|E^{\prime }\right|$ 。Kemnitz [5] [6]等人对色束缚数和边色数相等的图进行考虑，并给出了一般性结论，其中色束缚数指的是任意两个色类之间的最小边数，给出了f-边稳定数上界和下界的一般性结论，考虑了当图G满足$f={\chi }^{\prime }\left(G\right)$ 时特定图类的色边稳定数。Akbari [7]等人在图G满足

$\chi \left(G\right)\in \left\{\Delta \left(G\right),\Delta \left(G\right)+1\right\}$

的条件下证明了

$v{s}_{\chi }\left(G\right)=iv{s}_{\chi }\left(G\right)$

其中$iv{s}_{\chi }\left(G\right)$ 是独立色点稳定数，即使得色数$\chi \left(G\right)$ 改变的独立集的最小点数；同时也给出了当图G满足

$\chi \left(G\right)\ge \frac{\Delta \left(G\right)+1}{2}$

则有$v{s}_{\chi }\left(G\right)=e{s}_{\chi }\left(G\right)$ 成立。

文献[8] [9]中根据图的最大度给出了图G边色稳定数的严格上界，并考虑了$e{s}_{\chi }\left(G\right)=1$ 的图和k小于等于5的k正则图的特征描述。Kemnitz and Marangio [10]给出了一些关于f-点稳定数的一般性结论，并利用f-点稳定数对著名的Gallai定理进行了证明，同时关注了色数这一结构参数，通过一系列的图确定了色数点稳定数，其次考虑了色边稳定数和色点稳定数的关系，证明了它们的差和比率可以变成任意大。

本文利用图不变量f的性质，如可加性，可乘性等，进一步给出了笛卡尔积图f-点稳定数的相关结论，在不同条件下，通过f-点稳定数探究了笛卡尔积图与子图之间的关系。第二部分给出了定理证明需要的相关引理以及相关的定义。第三部分给出了笛卡尔积图f-点稳定数的界。

2. 相关定义和引理

定义2.1 [5]. 设图$G=H_1\cup H_2$ 且$H_1$ 和$H_2$ 是两个互不相交的图。若不变量f满足

$f\left(G\right)=f\left(H_1\cup H_2\right)=f\left(H_1\right)+f\left(H_2\right)$ ，

则称不变量f具有可加性。

定义2.2. 设图$G=H_1\cup H_2$ 且$H_1$ 和$H_2$ 是两个互不相交的图。若不变量f满足

$f\left(G\right)=f\left(H_1\cup H_2\right)=f\left(H_1\right)\cdot f\left(H_2\right)$ ，

则称不变量f具有可乘性。

定义2.3 [5]. 设图$G=H_1\cup H_2$ 且$H_1$ 和$H_2$ 是两个互不相交的图。若不变量f满足

$f\left(G\right)=f\left(H_1\cup H_2\right)=\max \left\{f\left(H_1\right),f\left(H_2\right)\right\}$ ，

则称不变量f具有最大性。

定义2.4. 设图$G=H_1\cup H_2$ 且$H_1$ 和$H_2$ 是两个互不相交的图。若不变量f满足

$f\left(G\right)=f\left(H_1\cup H_2\right)=\min \left\{f\left(H_1\right),f\left(H_2\right)\right\}$ ，

则称不变量f具有最小性。

定义2.5. 设图的f-点稳定数$v{s}_f\left(G\right)$ 定义为

$v{s}_f\left(G\right)=\{\begin{array}{l}\infty ,f\left(G-V^{\prime }\right)=f\left(G\right)且对所有的点子集V^{\prime }\subseteq V\left(G\right);\\ \min \left\{\left|V^{\prime }\right|:V^{\prime }\subseteq V\left(G\right)且f\left(G-V^{\prime }\right)\ne f\left(G\right)\right\},其它.\end{array}$

引理2.6 [10]. 若$V^{\prime }$ 是图G的一个点子集，则有

$v{s}_f\left(G\right)\le \left|V^{\prime }\right|+v{s}_f\left(G-V^{\prime }\right)$ 。

定义2.7. 设图H是图G的一个子图，f是一个图不变量，若有

$f\left(G\right)\ge f\left(H\right)$ ，

则称不变量f是单调递增的；反之，则称不变量f是单调递减的。

定义2.8 [11]. 设$G_1,G_2$ 是两个简单图，图G是由$G_1$ 和$G_2$ 构成的笛卡尔积图，记作

$G=G_1\square G_2$ ，

其中，定义图G顶点集为

$V\left(G\right)=V\left(G_1\right)\times \left(G_2\right)$ ，

其边集为

$E\left(G\right)=\left\{\left(u_1,v_1\right)\left(u_2,v_2\right):u_1=u_2且v_1{v}_2\in E\left(G_2\right)\vee v_1=v_2且u_1{u}_2\in E\left(G_1\right)\right\}$ 。

3. 笛卡尔积图的f-点稳定数的界

定理3.1. 设$H_1,H_2$ 是两个互不相交的图，$G=H_1\square H_2$ 且不变量f满足可加性。若图G中存在一个点集$V^{\prime }$ 使得$G-V^{\prime }=H_i\cup G^{\prime }$ ，$i=1,2$ ，则有

$v{s}_f\left(G\right)\le \left|V^{\prime }\right|+\min \left\{v{s}_f\left(H_i\right):i=1,2\right\}$ 。

证明 若图$H_i\left(i=1,2\right)$ 中找不到任何点集使得$f\left(H_i\right)$ 改变，由定义可知$v{s}_f\left(H_i\right)=\infty$ ，结论显然成立。

设

$v{s}_f\left(H_1\right)=\min \left\{v{s}_f\left(H_1\right):i=1,2\right\}$ ，

令$V^{″}\subseteq V\left(H_1\right)$ 是图$H_1$ 的一个点子集，使得$v{s}_f\left(H_1\right)=\left|V^{″}\right|$ ，则有

$f\left(H_1-V^{″}\right)\ne f\left(H_1\right)$ 。

现设图G存在一个点子集$V^{\prime }$ 且$G-V^{\prime }=H_1\cup G^{\prime }$ ，根据不变量f的可加性条件，得到

$\begin{array}{l}f\left(G-V^{\prime }-V^{″}\right)=f\left(\left(H_1-V^{″}\right)\cup G^{\prime }\right)=f\left(H_1-V^{″}\right)+f\left(G^{\prime }\right)\\ \ne f\left(H_1\right)+f\left(G^{\prime }\right)=f\left(H_1\cup G^{\prime }\right)\\ =f\left(G-V^{\prime }\right)\end{array}$

由定义可知

$v{s}_f\left(G-V^{\prime }\right)\le \left|V^{″}\right|=v{s}_f\left(H_1\right)$ ，

根据引理2.6有

$v{s}_f\left(G\right)\le v{s}_f\left(G-V^{\prime }\right)+\left|V^{\prime }\right|\le v{s}_f\left(H_1\right)+\left|V^{\prime }\right|$ 。

同理当$G-V^{\prime }=H_2\cup G^{\prime }$ 时，有

$v{s}_f\left(G\right)\le v{s}_f\left(G-V^{\prime }\right)+\left|V^{\prime }\right|\le v{s}_f\left(H_2\right)+\left|V^{\prime }\right|$ ，

则

$v{s}_f\left(G\right)\le \left|V^{\prime }\right|+\min \left\{v{s}_f\left(H_i\right):i=1,2\right\}$ 。 □

定理3.2. 设$H_1,H_2$ 是两个互不相交的图，$G=H_1\square H_2$ ，不变量f满足可乘性且非零。若图G中存在一个点集$V^{\prime }$ 使得$G-V^{\prime }=H_i\cup G^{\prime }$ ，$i=1,2$ ，则有

$v{s}_f\left(G\right)\le \left|V^{\prime }\right|+\min \left\{v{s}_f\left(H_i\right):i=1,2\right\}$ 。

证明 若$v{s}_f\left(H_i\right)=\infty$ ，$i=1,2$ ，则结论显然成立。

现证$v{s}_f\left(H_i\right)<\infty$ 的情况，令

$v{s}_f\left(H_1\right)=\min \left\{v{s}_f\left(H_i\right):i=1,2\right\}$ ，

若存在点子集$V^{″}\subseteq V\left(H_1\right)$ ，使得$v{s}_f\left(H_1\right)=\left|V^{″}\right|$ ，则

$f\left(H_1-V^{″}\right)\ne f\left(H_1\right)$ 。

由于图G是$H_1,H_2$ 构成的笛卡尔积图，存在一个点子集$V^{\prime }\in V\left(G\right)$ ，使得$G-V^{\prime }=H_1\cup G^{\prime }$ 。根据不变量f的可乘性条件且非零，则

$\begin{array}{l}f\left(G-V^{\prime }-V^{″}\right)=f\left(\left(H_1-V^{″}\right)\cup G^{\prime }\right)=f\left(H_1-V^{″}\right)\cdot f\left(G^{\prime }\right)\\ \ne f\left(H_1\right)\cdot f\left(G^{\prime }\right)=f\left(H_1\cup G^{\prime }\right)\\ =f\left(G-V^{\prime }\right)\end{array}$

由定义可知

$v{s}_f\left(G-V^{\prime }\right)\le \left|V^{″}\right|=v{s}_f\left(H_1\right)$ ，

根据引理2.6有

$v{s}_f\left(G\right)\le v{s}_f\left(G-V^{\prime }\right)+\left|V^{\prime }\right|\le v{s}_f\left(H_1\right)+\left|V^{\prime }\right|$ 。

同理当

$v{s}_f\left(H_2\right)=\min \left\{v{s}_f\left(H_i\right):i=1,2\right\}$ ，

有

$v{s}_f\left(G\right)\le v{s}_f\left(G-V^{\prime }\right)+\left|V^{\prime }\right|\le v{s}_f\left(H_2\right)+\left|V^{\prime }\right|$ ，

得

$v{s}_f\left(G\right)\le \left|V^{\prime }\right|+\min \left\{v{s}_f\left(H_i\right):i=1,2\right\}$ 。 □

定理3.3. 设$H_1,H_2$ 是两个互不相交的图，$G=H_1\square H_2$ ，不变量f满足最大性。若图G中存在一个点集$V^{\prime }$ 使得$G-V^{\prime }=H_i\cup G^{\prime }$ 且$f\left(H_i\right)>f\left(G^{\prime }\right)$ ，$i=1,2$ ，则有

$v{s}_f\left(G\right)\le \left|V^{\prime }\right|+\min \left\{v{s}_f\left(H_i\right):i=1,2\right\}$ 。

证明 根据引理2.6有

$v{s}_f\left(G\right)\le v{s}_f\left(G-V^{\prime }\right)+\left|V^{\prime }\right|$ ，

只需证

$v{s}_f\left(G-V^{\prime }\right)\le \min \left\{v{s}_f\left(H_i\right):i=1,2\right\}$ 。

若$v{s}_f\left(H_i\right)=\infty$ ，$i=1,2$ ，结论显然成立。

现设

$\min \left\{v{s}_f\left(H_i\right):i=1,2\right\}=v{s}_f\left(H_1\right)$ ，

令$V^{″}$ 是图$H_1$ 的点子集，使得$v{s}_f\left(H_1\right)=\left|V^{″}\right|$ ，则有

$f\left(H_1-V^{″}\right)\ne f\left(H_1\right)$ 。

又根据不变量f的最大性条件，有

$\begin{array}{l}f\left(G-V^{\prime }\right)=f\left(H_1\cup G^{\prime }\right)=\max \left\{f\left(H_1\right),f\left(G^{\prime }\right)\right\}=f\left(H_1\right)\\ \ne \max \left\{f\left(H_1-V^{″}\right),f\left(G^{\prime }\right)\right\}\\ =f\left(G-V^{\prime }-V^{″}\right)\end{array}$

由定义可得

$v{s}_f\left(G-V^{\prime }\right)\le \left|V^{″}\right|=v{s}_f\left(H_1\right)$ 。

同理当

$\min \left\{v{s}_f\left(H_i\right):i=1,2\right\}=v{s}_f\left(H_2\right)$ ，

有

$v{s}_f\left(G-V^{\prime }\right)\le \left|V^{″}\right|=v{s}_f\left(H_2\right)$ ，

则

$v{s}_f\left(G\right)\le \left|V^{\prime }\right|+\min \left\{v{s}_f\left(H_i\right):i=1,2\right\}$ 。 □

定理3.4. 设$H_1,H_2$ 是两个互不相交的图，$G=H_1\square H_2$ ，不变量f满足最小性。若图G中存在一个点集$V^{\prime }$ 使得$G-V^{\prime }=H_i\cup G^{\prime }$ 且$f\left(H_i\right)<f\left(G^{\prime }\right)$ ，$i=1,2$ ，则有

$v{s}_f\left(G\right)\le \left|V^{\prime }\right|+\min \left\{v{s}_f\left(H_i\right):i=1,2\right\}$ 。

证明 若$v{s}_f\left(H_i\right)=\infty$ ，$i=1,2$ ，则结论成立。

设存在$v{s}_f\left(H_i\right)<\infty$ ，可以令

$\min \left\{v{s}_f\left(H_i\right):i=1,2\right\}=v{s}_f\left(H_1\right)$ ，

若$V^{″}$ 是一个点子集且$V^{″}\subseteq V\left(H_1\right)$ ，使得$v{s}_f\left(H_1\right)=\left|V^{″}\right|$ ，则有

$f\left(H_1-V^{″}\right)\ne f\left(H_1\right)$ 。

根据不变量f的最小性条件，有

$\begin{array}{l}f\left(G-V^{\prime }\right)=f\left(H_1\cup G^{\prime }\right)=\min \left\{f\left(H_1\right),f\left(G^{\prime }\right)\right\}=f\left(H_1\right)\\ \ne \min \left\{f\left(H_1-V^{″}\right),f\left(G^{\prime }\right)\right\}\\ =f\left(G-V^{\prime }-V^{″}\right)\end{array}$

因此，可得

$v{s}_f\left(G-V^{\prime }\right)\le \left|V^{″}\right|=v{s}_f\left(H_1\right)$ 。

同理当

$\min \left\{v{s}_f\left(H_i\right):i=1,2\right\}=v{s}_f\left(H_2\right)$ ，

有

$v{s}_f\left(G-V^{\prime }\right)\le \left|V^{″}\right|=v{s}_f\left(H_2\right)$ ，

则

$v{s}_f\left(G\right)\le \left|V^{\prime }\right|+\min \left\{v{s}_f\left(H_i\right):i=1,2\right\}$ 。 □

通过上述定理可知，我们考虑的是两个不交图构成的笛卡尔积图，由此可以推广到多个不交图所构成的笛卡尔积图的f-点稳定数。

定理3.5. 设不变量f满足可加性且非零，$G_1=H_{11}\cup H_{12}\cup \cdots \cup H_{1n}$ ，$G_2=H_{21}\cup H_{22}\cup \cdots \cup H_{2m}$ ，$n,m$ 是正整数，并且它们的子图都是互不相交的。令$G=G_1\square G_2$ ，若图G存在一个点子集$V^{\prime }$ 使得$G-V^{\prime }=G_t\cup G^{\prime }$ ，$t=1,2$ ，则有

$v{s}_f\left(G\right)\le \left|V^{\prime }\right|+\min \left\{v{s}_f\left(H_{tk}\right),\left|V\left(H_{tk}\right)\right|,v{s}_f\left(G^{\prime }\right),\left|V\left(G^{\prime }\right)\right|:t=1且1\le k\le n\vee t=2且1\le k\le m\right\}$ 。

证明 根据引理2.6，只需证

$v{s}_f\left(G-V^{\prime }\right)\le \min \left\{v{s}_f\left(H_{tk}\right),\left|V\left(H_{tk}\right)\right|,v{s}_f\left(G^{\prime }\right),\left|V\left(G^{\prime }\right)\right|:t=1且1\le k\le n\vee t=2且1\le k\le m\right\}$ 。

当$t=1$ 时，有

$G-V^{\prime }=G_1\cup G^{\prime }$ ，

当$v{s}_f\left(H_{1n}\right)<\infty$ 且$v{s}_f\left(G^{\prime }\right)<\infty$ ，令

$\min \left\{v{s}_f\left(H_{tk}\right),\left|V\left(H_{tk}\right)\right|,v{s}_f\left(G^{\prime }\right),\left|V\left(G^{\prime }\right)\right|:t=1且1\le k\le n\vee t=2且1\le k\le m\right\}=v{s}_f\left(H_{1k}\right)$ ，

其中$1\le k\le n$ ，令$V^{″}$ 是一个点子集且$V^{″}\subseteq V\left(H_{1k}\right)$ ，使得$v{s}_f\left(H_{1k}\right)=\left|V^{″}\right|$ ，则有

$f\left(H_{1k}-V^{″}\right)\ne f\left(H_{1k}\right)$ 。

又根据不变量f的可加性条件，得

$\begin{array}{l}f\left(G-V^{\prime }-V^{″}\right)=f\left(H_{11}\right)+f\left(H_{12}\right)+\cdots +f\left(H_{1k}-V^{″}\right)+\cdots +f\left(H_{1n}\right)+f\left(G^{\prime }\right)\\ \ne f\left(H_{11}\right)+f\left(H_{12}\right)+\cdots +f\left(H_{1k}\right)+\cdots +f\left(H_{1n}\right)+f\left(G^{\prime }\right)\\ =f\left(G-V^{\prime }\right)\end{array}$

由定义有

$v{s}_f\left(G-V^{\prime }\right)\le \left|V^{″}\right|=vs\left(H_{1k}\right)$ 。

若

$\min \left\{v{s}_f\left(H_{tk}\right),\left|V\left(H_{tk}\right)\right|,v{s}_f\left(G^{\prime }\right),\left|V\left(G^{\prime }\right)\right|:t=1且1\le k\le n\vee t=2且1\le k\le m\right\}=\left|V\left(H_{1k}\right)\right|$ ，

其中$1\le k\le n$ ，则$v{s}_f\left(H_{1k}\right)=\infty$ 。不变量f满足可加性且不为零，有

$\begin{array}{l}f\left(G-V^{\prime }-V\left(H_{1i}\right)\right)=f\left(H_{11}\right)+f\left(H_{12}\right)+\cdots +f\left(H_{1k-1}\right)+f\left(H_{1k+1}\right)+\cdots +f\left(G^{\prime }\right)\\ \ne f\left(H_{11}\right)+f\left(H_{12}\right)+\cdots +f\left(H_{1k}\right)+\cdots +f\left(G^{\prime }\right)\\ =f\left(G-V^{\prime }\right)\end{array}$

得

$v{s}_f\left(G-V^{\prime }\right)\le \left|V\left(H_{1k}\right)\right|$ 。

同理，当$t=2$ 或

$\min \left\{v{s}_f\left(H_{tk}\right),\left|V\left(H_{tk}\right)\right|,v{s}_f\left(G^{\prime }\right),\left|V\left(G^{\prime }\right)\right|:t=1且1\le k\le n\vee t=2且1\le k\le m\}\right\}=\min \left\{v{s}_f\left(G^{\prime }\right),\left|V\left(G^{\prime }\right)\right|\right\}$ ，

得

$v{s}_f\left(G-V^{\prime }\right)\le \min \left\{\left|V\left(H_{2k}\right)\right|,v{s}_f\left(H_{2k}\right)\right\}$ 或$v{s}_f\left(G-V^{\prime }\right)\le \min \left\{v{s}_f\left(G^{\prime }\right),\left|V\left(G^{\prime }\right)\right|\right\}$

根据引理2.6，则有

$v{s}_f\left(G\right)\le \left|V^{\prime }\right|+\min \left\{v{s}_f\left(H_{tk}\right),\left|V\left(H_{tk}\right)\right|,v{s}_f\left(G^{\prime }\right),\left|V\left(G^{\prime }\right)\right|:t=1且1\le k\le n\vee t=2且1\le k\le m\right\}$ 。 □

定理3.6. 设不变量f单调递增且满足最大性，$G_1=H_{11}\cup H_{12}\cup \cdots \cup H_{1n}$ ，$G_2=H_{21}\cup H_{22}\cup \cdots \cup H_{2m}$ ，$n,m$ 是正整数，它们的子图都互不相交。令$G=G_1\square G_2$ ，存在一个点子集$V^{\prime }\subseteq V\left(G\right)$ 使得$G-V^{\prime }=G_t\cup G^{\prime }$ ，$t=1,2$ ，且$f\left(G-V^{\prime }\right)\ne f\left(G^{\prime }\right)$ 。若$f\left(H_{ts}\right)=f\left(G-V^{\prime }\right)$ ，$s,l$ 是正实数且$1\le s\le l<n$ 或m，则有

$v{s}_f\left(G\right)\le \left|V^{\prime }\right|+{\displaystyle {\sum }_{s=1}^l\min \left\{v{s}_f\left(H_{ts}\right),\left|V\left(H_{ts}\right)\right|\right\}}$ 。

证明 根据引理2.6，只需证

$v{s}_f\left(G-V^{\prime }\right)\le {\displaystyle {\sum }_{s=1}^l\min \left\{v{s}_f\left(H_{ts}\right),\left|V\left(H_{ts}\right)\right|\right\}}$ 。

当$t=1$ 时，令$V^{\prime }$ 是一个点子集且$V^{\prime }\subseteq V\left(G\right)$ ，使得

$G-V^{\prime }=G_1\cup G^{\prime }=H_{11}\cup H_{12}\cup \cdots \cup H_{1n}\cup G^{\prime }$ ，

设图$H_{1s}$ 是图$G-V^{\prime }$ 的子图，$s=1,2,\cdots ,l$ ，当$v{s}_f\left(H_{1s}\right)=\infty$ 时，令

$Y_s=V\left(H_{1s}\right)$ ；

当$v{s}_f\left(H_{1s}\right)<\infty$ 时，存在一个点子集$Y_s\in V\left(H_{1s}\right)$ 使得$\left|Y_s\right|=v{s}_f\left(H_{1s}\right)$ ，令

$f\left(H_{1s}-Y_s\right)\ne f\left(H_{1s}\right)$ 。

设T是一个点子集且$T\subseteq V\left(G-V^{\prime }\right)$ ，使得$T=Y_1\cup Y_2\cup \cdots \cup Y_l$ ，则

$\left|T\right|={\displaystyle {\sum }_{s=1}^l\min \left\{v{s}_f\left(H_{1s}\right),\left|V\left(H_{1s}\right)\right|\right\}}$ ，

根据不变量f的单调递增且满足最大性条件，有

$\begin{array}{l}f\left(G-V^{\prime }-T\right)=\max \left\{f\left(H_{11}-Y_1\right),f\left(H_{12}-Y_2\right),\cdots ,f\left(H_{1l}-Y_l\right),f\left(H_{1l+1}\right),\cdots ,f\left(H_{1n}\right),f\left(G^{\prime }\right)\right\}\\ \ne \max \left\{f\left(H_{11}\right),f\left(H_{12}\right),\cdots ,f\left(H_{1l}\right),f\left(H_{1l+1}\right),\cdots ,f\left(H_{1n}\right),f\left(G^{\prime }\right)\right\}\\ =f\left(G-V^{\prime }\right)\end{array}$

由定义得

$v{s}_f\left(G-V^{\prime }\right)\le \left|T\right|={\displaystyle {\sum }_{s=1}^l\min \left\{v{s}_f\left(H_{1s}\right),\left|V\left(H_{1s}\right)\right|\right\}}$ 。

当$t=2$ 时，同理可得

$v{s}_f\left(G-V^{\prime }\right)\le \left|T\right|={\displaystyle {\sum }_{s=1}^l\min \left\{v{s}_f\left(H_{2s}\right),\left|V\left(H_{2s}\right)\right|\right\}}$ ，

根据引理2.6有

$v{s}_f\left(G\right)\le \left|V^{\prime }\right|+v{s}_f\left(G-V^{\prime }\right)\le \left|V^{\prime }\right|+{\displaystyle {\sum }_{s=1}^l\min \left\{v{s}_f\left(H_{ts}\right),\left|V\left(H_{ts}\right)\right|\right\}}$ 。 □

4. 总结

本文通过图不变量的性质，研究了笛卡尔积图不变量点稳定数的界。近些年，关于不变量稳定数的研究也是热点问题之一，本文丰富了在笛卡尔积图方面的研究成果。目前关于图的不变量稳定数有较多结论，如图的色点稳定数、色边稳定数等，本文只考虑了笛卡尔积图不变量点稳定数，相对应的笛卡尔积图不变量边稳定数也可以进行研究。

基金项目

新疆自然科学基金项目(2024D01A89, 2022D03002)；国家自然科学基金地区科学基金项目(11961070)。

NOTES

^*通讯作者。