乘积图和F-Sum图的Steiner K-距离

Steiner K-Distances in Graph Products and F-Sum Graphs

摘要: 图的距离是图论中非常重要且基本的概念，是研究基于距离的图不变量的基础。Steiner距离是图论组合研究中的经典问题。本文运用Steiner树的定义证明了corona积的Steiner k-半径和cluster积的Steiner k-半径的上下界以及F-sum图的Steiner距离和Steiner k-直径的界。

Abstract: Graph distance is a very important and basic concept in graph theory, which is the basis of studying graph invariants based on distance. Steiner distance is a classic problem in graph theory com-binatorial research. This paper proves the upper and lower bounds of Steiner k-radius of corona product and cluster product and the bounds of Steiner distance and Steiner k-diameter of F-sum graphs by using the definition of Steiner tree.

1. 引言

图的Steiner问题是经典的组合优化问题。1989年，Chartrand等 [1] 引入了Steiner距离的概念并进行了初步的研究。Mao等 [2] 在2018年研究了笛卡尔积和字典序积的Steiner距离，并在Steiner距离的基础上给出了Steiner直径的上下界。2019年，Wang等 [3] 接着研究了阈值图、联结图、corona积、cluster积的Steiner距离和Steiner直径，引入了有关Steiner树的概念，运用Steiner树的结构特征证明了相关定理。其余有关Steiner距离的研究可参考Mao等 [4] [5] [6] ，Oellermann等 [7] 的工作。

乘积图的提出是基于这样一种思想，即利用乘积作为一种工具，将两个具有既定性质的已知图组合起来，得到一个新的图，该图继承了这两个图的性质。2009年，Eliasi等 [8] 引入了F-sum图的概念，研究了F-sum图的一般距离。本文对corona积，cluster积，F-sum图的Steiner半径、Steiner距离、Steiner直径进行研究。有关这三个乘积图 [9] - [18] 的一些参数及拓扑指数也得到了充分研究。

本文中所有图都是连通的简单无向图，且顶点个数至少为两个。假设G是一个连通图，顶点 $u,v\in V\left(H\right)$ ，则 $d_G\left(u,v\right)$ 表示顶点 $u,v$ 之间最短路的长度。令S是G的一个非空集合且 $\left|S\right|=k$ $\left(2\le k\le n\right)$ 。点集S的Steiner距离 $d_G\left(S\right)$ 表示包含S的最小连通子图的边数，特别地，这个最小的连通子图一定是一颗树，令它为S-Steiner树。令k是一个整数且 $2\le k\le n$ ，则图G中顶点v的Steiner k-离心率 $e_k\left(v\right)$ 被定义为 $e_k\left(v\right)=\max \left\{d_G\left(S\right)|S\subseteq V\left(G\right),\left|S\right|=k且v\in S\right\}$ 。此外，Steiner k-直径和Steiner k-半径的定义为 $sdia{m}_k\left(G\right)=\max \left\{e_k\left(v\right)|v\in V\left(G\right)\right\}$ 和 $sra{d}_k\left(G\right)=\min \left\{e_k\left(v\right)|v\in V\left(G\right)\right\}$ 。连通图G的中心 $C\left(G\right)$ 是由 $e\left(v\right)=rad\left(G\right)$ 的顶点v诱导的子图，作为图中心的推广，连通图G的Steiner k-中心 $C_k\left(G\right)$ 是由最小Steiner k-离心率顶点导出的子图，其中 $e_k\left(v\right)=sra{d}_k\left(G\right)$ 。

Corona积，Cluster积 [19] 和F-sum图 [8] 的定义如下：

定义1 Corona积 $G\ast H$ 通过复制一个G，复制 $\left|V\left(G\right)\right|$ 个H，然后将复制的第i个H的每一个顶点与G的第个顶点连接起来，其中 $i=1,2,\cdots ,\left|V\left(G\right)\right|$ 。设G和H是两个连通图，顶点集分别为 $V\left(G\right)=\left\{g_1,g_2,\cdots ,g_n\right\}$ 和 $V\left(H\right)=\left\{h_1,h_2,\cdots ,h_m\right\}$ ，则 $G\ast H$ 的顶点集为 $V\left(G\ast H\right)=V\left(G\right)\cup \left\{\left(g_i,h_j\right)|1\le i\le n,1\le j\le m\right\}$ 。

定义2 Cluster积 $G\odot H$ 通过复制一个G，复制 $\left|V\left(G\right)\right|$ 个根图H，然后将复制的第i个根图H的根与G的第i个顶点相连，其中 $i=1,2,\cdots ,\left|V\left(G\right)\right|$ 。设G和H是两个连通图，顶点集分别为 $V\left(G\right)=\left\{g_1,g_2,\cdots ,g_n\right\}$ 和 $V\left(H\right)=\left\{h_1,h_2,\cdots ,h_m\right\}$ ，则 $V\left(G\odot H\right)$ 的顶点集为 $V\left(G\odot H\right)=\left\{\left(g_i,h_j\right)|1\le i\le n,1\le j\le m\right\}$ 。

定义3 F-sum图 $G{+}_{F}H$ 的顶点集为 $V\left(G{+}_{F}H\right)=\left(V\left(G\right)\cup E\left(G\right)\right)\times V\left(H\right)$ 。 $G{+}_{F}H$ 中的两个顶点分别为 $\left(g_1,g_2\right)$ 和 $\left(h_1,h_2\right)$ ，这两个顶点相邻当且仅当 $g_1=h_1\in V\left(G\right)$ 且 $\left(g_2,h_2\right)\in E\left(H\right)$ 或者 $g_2=h_2$ 且 $\left(g_1,h_1\right)\in E\left(F\left(G\right)\right)$ 。 $S,R,Q$ 和T的定义如下：

$S\left(G\right)$ ：在图中的每条边上添加一个新的顶点，使得每条边都由长度为2的路替换所得的图。

$R\left(G\right)$ ：在图G中的每条边上添加一个新的顶点，在图G的基础上，将每个新顶点连接到相应边的端点上所得的图。

$Q\left(G\right)$ ：在图G中的每条边上添加一个新的顶点，将新顶点与相邻的顶点相连所得的图。

$T\left(G\right)$ ：将 $R\left(G\right)$ 和 $Q\left(G\right)$ 结合所得的图。

其中，F代表图变换 $S,R,Q$ 和T中的一个。

下面给出两个重要的引理。

引理1 [3] G和H是两个连通图，其中 $V\left(G\right)=\left\{g_1,g_2,\cdots ,g_n\right\}$ ， $V\left(H\right)=\left\{h_1,h_2,\cdots ,h_m\right\}$ 。令 $k,m,n$ 是三个整数且 $3\le k\le n\left(m+1\right)$ 。S是 $G\ast H$ 的顶点各不相同的集合，使得 $\left|S\right|=k$ 。则有

$d_{G*H}\left(S\right)=d_G\left({S^{\prime }}_G\right)+k-t$ ，

其中 $\left|S\cap V\left(G\right)\right|=t$ ， ${S^{\prime }}_G$ 是 $V\left(G\right)$ 的最大子集使得对于任意的 $g\in {S^{\prime }}_G$ 都有 $S\cap \left(V\left(H\left(g\right)\right)\cup g\right)\ne \varnothing$ 。

引理2 [3] 令点集S是Cluster积 $G\odot H$ 的一个顶点各不相同的顶点集，如果存在 $S\subseteq V\left(H\left(g_i\right)\right)$ 中的顶点在不同的 $H\left(g_i\right)$ $\left(1\le i\le n\right)$中，则

$d_G\left({S^{\prime }}_G\right)+k-t\le d_{G\odot H}\left(S\right)\le r\cdot d_H\left({S^{\prime }}_H\right)+d_G\left({S^{\prime }}_G\right)$ ，

其中，当 $h_1\in S_H$ ， ${S^{\prime }}_H=S_H\cup \left\{h_1\right\}$ 时，有 ${S^{\prime }}_H=S_H$ 。否则，令 $\left|S\cap V\left(G\left(h_1\right)\right)\right|=t$ ， $\left|{S^{\prime }}_G\right|=r$ ， ${S^{\prime }}_G$ 是 $V\left(G\right)$ 的最大的子集使得对每一个 $g\in {S^{\prime }}_G$ 都有 $S\cap V\left(H\left(g\right)\right)\ne \varnothing$ 。

2. 主要结果

2.1. Corona积和Cluster积的Steiner k-半径

定理1 令 $k,m,n$ 是三个整数且 $3\le k\le n\left(m+1\right)$ ，连通图 $G,H$ 分别有n和m个顶点。

如果 $3\le k\le n$ ，那么 $sra{d}_k\left(G\ast H\right)=sra{d}_k\left(G\right)+k-1$ 。

如果 $n+1\le k\le mn$ ，那么 $sra{d}_k\left(G\ast H\right)=\left(n-1\right)+\left(k-1\right)$ 。

如果 $mn+1\le k\le \left(m+1\right)n$ ，那么 $sra{d}_k\left(G\ast H\right)=mn+n-1$ 。

证明 以上三种情况的证明方法相同，这里仅考虑第二种情况。如果 $n+1\le k\le mn$ ，根据 $sra{d}_k\left(G\ast H\right)$ 的定义，可以发现存在一个顶点子集 $S\subseteq V\left(G\ast H\right)$ ，并且 $\left|S\right|=k$ 使得 $d_{G\ast H}\left(S\right)=sra{d}_k\left(G\ast H\right)$ 。令 $S=\left\{\left(g_{i_1},h_{j_1}\right),\left(g_{i_2},h_{j_2}\right),\cdots ,\left(g_{i_{k-1}},h_{j_{k-1}}\right)\right\}\cup \left\{g_i\right\}$ $\left(g_i\in C_k\left(G\right)\right)$ ，其中 ${S^{\prime }}_G\subseteq \left\{g_{i_1},g_{i_2},\cdots ,g_{i_{k-1}}\right\}\cup \left\{g_i\right\}$ 。当 $\left|S\cap V\left(G\right)\right|=t$ 时，由引理1可得

$sra{d}_k\left(G\ast H\right)=d_{G\ast H}\left(S\right)=d_G\left({S^{\prime }}_G\right)+k-t\le \left(n-1\right)+\left(k-1\right)$ (1)

另一方面，选择 $S=\left\{\left(g_{i_1},h_{j_1}\right),\left(g_{i_2},h_{j_2}\right),\cdots ,\left(g_{i_{k-1}},h_{j_{k-1}}\right)\right\}\cup \left\{g_i\right\}$ 使得 $V\left(G\right)\subseteq \left\{g_{i_1},g_{i_2},\cdots ,g_{i_{k-1}}\right\}\cup \left\{g_i\right\}$ $\left(g_i\in C_k\left(G\right)\right)$ 。则任意的S-Steiner树T一定包含 $S_G=V\left(G\right)$ 中的所有顶点(树T的大小至少是 $n-1$ )，且令T的子树为 $T^{\prime }$ 。对于 $S-\left\{g_i\right\}$ 中的每一个顶点，至少需要一条边去连接它和 $T^{\prime }-\left\{g_i\right\}$ 中的顶点，因此可以得到

$sra{d}_k\left(G\ast H\right)\ge d_{G\ast H}\left(S\right)\ge d_G\left(S_G\right)+k-1=\left(n-1\right)+\left(k-1\right)$ (2)

由不等式(1)和(2)，可以得出结论 $sra{d}_k\left(G\ast H\right)=\left(n-1\right)+\left(k-1\right)$ 。

定理2 令 $k,m$ 和n三个正整数且 $3\le k\le nm$ ，令连通图 $G,H$ 分别有 $n,m$ 个顶点。

如果 $3\le k\le \text{min}\left\{n,m\right\}$ ，那么

$sra{d}_k\left(G\right)+k-1\le sra{d}_k\left(G\odot H\right)\le \left(k-1\right)sra{d}_k\left(H\right)+sra{d}_k\left(G\right)$ 。

如果 $m>n$ 并且 $n+1\le k\le m-1$ ，那么

$\left(n-1\right)+\left(k-1\right)\le sra{d}_k\left(G\odot H\right)\le n\cdot sra{d}_k\left(H\right)+\left(n-1\right)$ 。

如果 $m\le n$ 并且 $m+1\le k\le n-1$ ，那么

$sra{d}_k\left(G\right)+k-1\le sra{d}_k\left(G\odot H\right)\le \left(k-1\right)\left(m-1\right)+sra{d}_k\left(G\right)$ 。

如果 $\text{max}\left\{n,m\right\}\le k\le nm-n$ ，那么

$\left(n-1\right)+\left(k-1\right)\le sra{d}_k\left(G\odot H\right)\le mn-1$ 。

如果 $nm-n<k\le mn$ ，那么

$sra{d}_k\left(G\odot H\right)=nm-1$ 。

证明 首先讨论 $sra{d}_k\left(G\odot H\right)$ 以上五种情况的上界。根据 $sra{d}_k\left(G\odot H\right)$ 的定义，可知存在一个顶点子集 $S\subseteq V\left(G\odot H\right)$ 且 $\left|S\right|=k$ ，使得 $d_{G\odot H}\left(S\right)=sra{d}_k\left(G\odot H\right)$ 。令 $S=\left\{\left(g_{i_1},h_{j_1}\right),\left(g_{i_2},h_{j_2}\right),\cdots ,\left(g_{i_{k-1}},h_{j_{k-1}}\right)\right\}\cup \left\{\left(g_{i_k},h_1\right)\right\}$ ， $\left(\left(g_{i_k},h_1\right)\in \left(C_k\left(G\odot H\right)\cap V\left(G\right)\right)\right)$ 。其中 $S_G=\left\{g_{i_1},g_{i_2},\cdots ,g_{i_{k-1}}\right\}\cup \left\{g_{i_k}\right\}$ 且 $S_H=\left\{h_{j_1},h_{j_2},\cdots ,h_{j_{k-1}}\right\}$ 。由引理2可得 $sra{d}_k\left(G\right)=d_{G\odot H}\left(S\right)\le r\cdot d_H\left({S^{\prime }}_H\right)+d_G\left({S^{\prime }}_G\right)$ 。

首先证明结论a)。如果 $3\le k\le \text{min}\left\{n,m\right\}$ ，则有 $d_H\left(S_H\cup \left\{h_1\right\}\right)=d_H\left({S^{\prime }}_H\right)\le sra{d}_k\left(H\right)$ ， $d_G\left({S^{\prime }}_G\right)=d_G\left(S_G\right)\le sra{d}_k\left(G\right)$ ，并且 $r=k-1$ 。因此

$sra{d}_k\left(G\odot H\right)=d_{G\odot H}\left(S\right)\le r\cdot d_H\left({S^{\prime }}_H\right)+d_G\left({S^{\prime }}_G\right)\le \left(k-1\right)sra{d}_k\left(H\right)+sra{d}_k\left(G\right)$ 。

其次证明结论b)。如果 $m>n$ 且 $n+1\le k\le m-1$ ，则有 $d_G\left({S^{\prime }}_G\right)=d_G\left(S_G\right)\le n-1$ ，并且 $r=n$ 。因此

$sra{d}_k\left(G\odot H\right)=d_{G\odot H}\left(S\right)\le r\cdot d_H\left({S^{\prime }}_H\right)+d_G\left({S^{\prime }}_G\right)\le n\cdot sra{d}_k\left(H\right)+\left(n-1\right)$ 。

接着证明结论c)。如果 $m<n$ 且 $m+1\le k\le n-1$ ，可知 $d_H\left(S_H\cup \left\{h_1\right\}\right)=d_H\left({S^{\prime }}_H\right)\le m-1$ ， $d_G\left({S^{\prime }}_G\right)=d_G\left(S_G\right)\le sra{d}_k\left(G\right)$ ，并且 $r=k-1$ 。因此

$sra{d}_k\left(G\odot H\right)=d_{G\odot H}\left(S\right)\le r\cdot d_H\left({S^{\prime }}_H\right)+d_G\left({S^{\prime }}_G\right)\le \left(k-1\right)\left(m-1\right)+sra{d}_k\left(G\right)$ 。

然后证明结论d)。如果 $\text{max}\left\{n,m\right\}\le k\le nm-n$ ，可知 $d_H\left(S_H\cup \left\{h_1\right\}\right)=d_H\left({S^{\prime }}_H\right)\le m-1$ ， $d_G\left({S^{\prime }}_G\right)=d_G\left(S_G\right)\le n-1$ ，并且 $r=n$ 。因此

$sra{d}_k\left(G\odot H\right)=d_{G\odot H}\left(S\right)\le r\cdot d_H\left({S^{\prime }}_H\right)+d_G\left({S^{\prime }}_G\right)\le n\left(m-1\right)+\left(n-1\right)=nm-1$ 。

最后证明结论e)。显然可以得到 $sra{d}_k\left(G\odot H\right)\le nm-1$ 。

另一方面，由引理2可知 $d_G\left({S^{\prime }}_G\right)+k-t\le d_{G\odot H}\left(S\right)\le sra{d}_{G\odot H}\left(S\right)$ 。且令 $S_G=\left\{g_{i_1},g_{i_2},\cdots ,g_{i_{k-1}}\right\}\cup \left\{g_{i_k}\right\}={S^{\prime }}_G$ ， $S_H=\left\{h_{j_1},h_{j_2},\cdots ,h_{j_{k-1}}\right\}$ 。对结论a)的下界进行证明，如果 $3\le k\le \text{min}\left\{n,m\right\}$ ，对于任意的S-Steiner树T一定包含 $S_G$ 中的所有顶点(树T的大小至少是 $d_G\left(S_G\right)$ )，假设树T有子树 $T^{\prime }$ 。对于每一个 $S-\left(g_{i_k},h_1\right)$ 中的顶点，需要至少一条边来连接它和 $T^{\prime }-\left\{g_{i_k}\right\}$ 中的顶点，最终得到

$sra{d}_k\left(G\odot H\right)\ge d_{G\odot H}\left(S\right)\ge sra{d}_k\left(G\right)+k-t\ge sra{d}_k\left(G\right)+k-1$ 。

结论b)和结论e)的证明与结论a)的证明类似。对于c)和d)中的情况，证明过程与其上界的证明完全一样。

推论1 假设 $G=P_n$ ， $H=P_m$ 且 $3\le k\le mn$ 。对每一个 $g_i\left(1\le i\le n\right)$ 有 $H\left(g_i\right)\cong P_m$ 和 $G\left(h_1\right)\cong P_n$ 。如果 $3\le k\le n$ ，则 $sra{d}_k\left(P_n\odot P_m\right)=\left(k-1\right)\left(m-1\right)+\left(n-1\right)$ ；如果 $n+1\le k\le nm$ ，则 $sra{d}_k\left(P_n\odot P_m\right)=nm-1$ 。

推论2 假设 $G=P_n$ ， $H=K_m$ 且 $3\le k\le mn$ 。对每一个 $g_i\left(1\le i\le n\right)$ 有 $H\left(g_i\right)\cong K_m$ 和 $G\left(h_1\right)\cong P_n$ 。如果 $3\le k\le mn-n+1$ ，则 $sra{d}_k\left(P_n\odot K_m\right)=\left(k-1\right)+\left(n-1\right)$ 。

2.2. F-Sum图的Steiner距离

令G和H是两个连通图，并且 $3\le k\le m\left(n+\epsilon \right)$ ( $\epsilon$ 是图G的边数)，k是一个整数。令 $S=\left\{\left(g_{i_1},h_{j_1}\right),\left(g_{i_2},h_{j_2}\right),\cdots ,\left(g_{i_k},h_{j_k}\right)\right\}$ 是F-sum图 $G{+}_{F}H$ 的一个顶点各不相同的顶点集，其中F代表 $S,R,Q$ 和T中的其中一个。首先介绍几个参数：

• 令 $H\left(g\right)$ $\left(g\in F\left(G\right)\right)$ 是H的一个复制，其中 $\left|H\left(g\right)\cap S\right|=r$ 。

• 令 $X_{F\left(G\right)}^i$ $\left(1\le i\le \left(\begin{array}{c}k\\ 3\end{array}\right)\right)$ 是集合 $\left\{g_{i_1},g_{i_2},\cdots ,g_{i_k}\right\}$ 的(k-3)-重子集，其中 $\left\{g_{i_1},g_{i_2},\cdots ,g_{i_k}\right\}\subset V\left(F\left(G\right)\right)$ 。令 $a_i$ 是 $X_{F\left(G\right)}^i$ 中每个集合中不同顶点的个数，其中 $a=\min \left\{a_i|1\le i\le \left(\begin{array}{c}k\\ 3\end{array}\right)\right\}$ 。

• 令 $Y_H^j$ $\left(1\le j\le \left(\begin{array}{c}k\\ 3\end{array}\right)\right)$ 是集合 $\left\{h_{j_1},h_{j_2},\cdots ,h_{j_k}\right\}$ 的(k-3)-重子集，其中 $\left\{h_{j_1},h_{j_2},\cdots ,h_{j_k}\right\}\subset V\left(H\right)$ 。令 $b_j$ 是 $Y_H^j$ 中每个集合中不同顶点的个数，其中 $b=\min \left\{b_j|1\le j\le \left(\begin{array}{c}k\\ 3\end{array}\right)\right\}$ 。

定理3 根据上面的定义，可以得到重集 $S_G=\left\{g_{i_1},g_{i_2},\cdots ,g_{i_k}\right\}$ 和 $S_H=\left\{h_{j_1},h_{j_2},\cdots ,h_{j_k}\right\}$ 。则

$\begin{array}{l}{d}_{F\left(G\right)}\left(S_G\right)+d_H\left(S_H\right)\le d_{G{+}_{F}H}\left(S\right)\\ \le \min \left\{r+d_{F\left(G\right)}\left(S_G\right)+\left(a+1\right)d_H\left(S_H\right),r+d_H\left(S_H\right)+\left(b+1\right)d_{F\left(G\right)}\left(S_H\right)\right\}\\ \le \min \left\{r+d_{F\left(G\right)}\left(S_G\right)+\left(k-2\right)d_H\left(S_H\right),r+d_H\left(S_H\right)+\left(k-2\right)d_{F\left(G\right)}\left(S_H\right)\right\}\\ =r+d_{F\left(G\right)}\left(S_G\right)+d_H\left(S_H\right)+\left(k-3\right)\min \left\{d_{F\left(G\right)}\left(S_H\right)+d_H\left(S_H\right)\right\}\end{array}$

证明 根据对称性，这里只考虑 $d_{G{+}_{F}H}\left(S\right)\le r+d_H\left(S_H\right)+\left(b+1\right)d_{F\left(G\right)}\left(S_G\right)$ 的情况。当 $V\left(H\right)=\left\{h_1,h_2,\cdots ,h_m\right\}$ ，假设 $F_G\left(h_1\right),F_G\left(h_2\right),\cdots ,F_G\left(h_r\right)$ 是 $F\left(G\right)$ 的r个复制，使得 $\left|V\left(F_G\left(h_j\right)\right)\cap S\right|\ne 0$ ， $1\le j\le r$ 。因此 $\left(g_{i_1},h_{j_1}\right),\left(g_{i_2},h_{j_2}\right),\cdots ,\left(g_{i_k},h_{j_k}\right)\in {\displaystyle \underset{j=1}{\overset{r}{\cup }}V}\left(F_G\left(h_j\right)\right)$ 。接下来，考虑三种情况：

情况1. $S_G\subseteq V\left(G\right)$ (S中的所以顶点都是实心的)且 $3\le k\le mn$ 。

由任意性，假设 $V\left(F_G\left(h_1\right)\right)\cap S=\left\{\left(g_{i_1},h_1\right),\left(g_{i_2},h_1\right),\cdots ,\left(g_{i_s},h_1\right)\right\}$ ，那么可以得到顶点 $\left(g_{i_{s+1}},h_{j_{s+1}}\right),\left(g_{i_{s+2}},h_{j_{s+2}}\right),\cdots ,\left(g_{i_k},h_{j_k}\right)\in {\displaystyle \underset{j=2}{\overset{r}{\cup }}V}\left(F_G\left(h_j\right)\right)$ 。 $F\left(G\right)$ 中存在一个大小为 $d_{F_G}\left(S_G\right)$ 的 $S_G$ -Steiner树，则在 $F_G\left(h_1\right)$ 中存在一个大小为 $d_{F_G}\left(S_G\right)$ 且包含顶点 $\left\{\left(g_{i_1},h_1\right),\left(g_{i_2},h_1\right),\cdots ,\left(g_{i_s},h_1\right)\right\}\cup \left(g_{i_{s+1}},h_1\right),\left(g_{i_{s+2}},h_1\right),\cdots ,\left(g_{i_k},h_1\right)$ 的Steiner树，令这个Steiner树为 $T\left(h_1\right)$ 。

每一个 $F_G\left(h_j\right)$ $\left(1\le j\le r\right)$ 都有一个相对应的Steiner树 $T\left(h_j\right)$ 。所以 $T\left(h_j\right)$ $\left(1\le j\le r\right)$ 是一个大小为 $d_{F_G}\left(S_G\right)$ 且包含 $F_G\left(h_j\right)$ 中的顶点 $\left\{\left(g_{i_1},h_j\right),\left(g_{i_2},h_j\right),\cdots ,\left(g_{i_s},h_j\right),\left(g_{i_{s+1}},h_j\right),\cdots ,\left(g_{i_k},h_j\right)\right\}$ 的Steiner树。同样的，H也有一个大小为 $d_H\left(S_H\right)$ 的 $S_H$ -Steiner树。因此 $T\left(g_{i_1}\right)$ 包含 $H\left(g_{i_1}\right)$ 中的顶点 $\left\{\left(g_{i_1},h_{j_1}\right),\left(g_{i_1},h_{j_2}\right),\cdots ,\left(g_{i_1},h_r\right)\right\}$ 并且大小为 $d_H\left(S_H\right)$ 的Steiner树(见图1)。

如果 $\left|V\left(F_G\left(h_j\right)\right)\cap S\right|\ge 2$ $\left(1\le j\le r\right)$，则 $G{+}_{F}H$ 的一个S-Steiner树是由边 $\left({\displaystyle \underset{j=y+1}{\overset{r}{\cup }}E}\left(T\left(h_j\right)\right)\right)\cup E\left(T\left(g_{i_1}\right)\right)$ 组成。由b的定义可得 $b=r$ 或 $b=r-1$ ，则有 $d_{G{+}_{F}H}(S)\le d_H(S_H)+(b+1)$ $d_{F(G)}(S_G)$ 。

Figure 1. All vertices in S are solid

图1. S中的所以顶点都是实心的

如果 $\left|V\left(F_G\left(h_j\right)\right)\cap S\right|=1$ ，其中 $1\le j\le y$ 。若 $y\ge 3$ ， $G{+}_{F}H$ 的一个S-Steiner树是由边 $\left({\displaystyle \underset{j=y+1}{\overset{r}{\cup }}E}\left(T\left(h_j\right)\right)\right)\cup E\left(T\left(g_{i_1}\right)\right)$ 组成，由b的定义可知 $b=r-3$ 。若 $y=1$ 或 $y=2$ ，则 $G{+}_{F}H$ 的一个S-Steiner 树是由边 $\left({\displaystyle \underset{j=2}{\overset{r}{\cup }}E}\left(T\left(h_j\right)\right)\right)\cup E\left(T\left(g_{i_1}\right)\right)$ 组成，根据b的定义，可以得到 $b=r-1$ 或者 $b=r-2$ ，则 $d_{G{+}_{F}H}\left(S\right)\le d_H\left(S_H\right)+\left(b+1\right)d_{F\left(G\right)}\left(S_G\right)$ 。

情况2. $S_G\subseteq E\left(G\right)$ (S中的所有顶点都是空心的)且 $3\le k\le m\epsilon$ 。

由任意性，假设 $V\left(F_G\left(h_1\right)\right)\cap S=\left\{\left(g_{i_1},h_1\right),\left(g_{i_2},h_1\right),\cdots ,\left(g_{i_s},h_1\right)\right\}$ 。则 $\left(g_{i_{s+1}},h_{j_{s+1}}\right),\left(g_{i_{s+2}},h_{j_{s+2}}\right),\cdots ,\left(g_{i_k},h_{j_k}\right)\in {\displaystyle \underset{j=2}{\overset{r}{\cup }}V}\left(F_G\left(h_j\right)\right)$ ，其中 $g_{i_1},g_{i_2},\cdots ,g_{i_k}\in E\left(G\right)$ 。

对于每一个 $F_G\left(h_j\right)$ $\left(1\le j\le r\right)$ 都有与之相对应的Steiner树 $T\left(h_j\right)$ 。因此 $T\left(h_j\right)$ $\left(1\le j\le r\right)$ 是大小为 $d_{F_G}\left(S_G\right)$ 且包含 $F_G\left(h_j\right)$ 中k个顶点的Steiner树。同样的，图H有一个大小为 $d_H\left(S_H\right)$ 的 $S_H$ -Steiner树，因此 $T\left(g_{i_1}\right)$ 是一个大小为 $d_H\left(S_H\right)$ 且包含 $H\left(g_{i_1}\right)$ 中的r个顶点的Steiner树(见图2)。

Figure 2. All vertices in S are hollow

图2. S中的所有顶点都是空心的

根据 $G{+}_{F}H$ 的定义，对于任意的两个顶点 $\left(g_{i_p},h_1\right)\in V\left(F_G\left(h_1\right)\right)$ 和 $\left(g_{i_p},h_{j_p}\right)\in V\left(F_G\left(h_{j_p}\right)\right)$ ，且 $d\left(\left(g_{i_p},h_1\right),\left(g_{i_p},h_{j_p}\right)\right)\ne 1$ 。因此不能直接连接 $F_G\left(h_j\right)$ 中的 $T\left(h_j\right)$ 和 $H\left(g_{i_1}\right)$ 中的 $T\left(g_{i_1}\right)$ 。由任意性，假设 $g_{i_1}=uv\in E\left(G\right)$ ， $d\left(u,g_{i_1}\right)=d\left(g_{i_1},v\right)=1$ ，即需要一条边去连接顶点u和 $T\left(h_j\right)$ $\left(1\le j\le r\right)$，那么 $T\left(h_j\right)$ $\left(1\le j\le r\right)$和 $T\left(g_{i_1}\right)$ 需要r条边去连接。

如果 $\left|V\left(F_G\left(h_j\right)\right)\cap S\right|\ge 2$ $\left(1\le j\le r\right)$，则 $G{+}_{F}H$ 的一个S-Steiner树是由边 $\left({\displaystyle \underset{j=1}{\overset{r}{\cup }}E}\left(T\left(h_j\right)\right)\right)\cup E\left(T\left(g_{i_1}\right)\right)\cup \left({\displaystyle \underset{j=1}{\overset{r}{\cup }}E}\left(u,T\left(h_j\right)\right)\right)$ 组成，根据b的定义可知 $b=r$ 或 $b=r-1$ ，则 $d_{G{+}_{F}H}\left(S\right)\le r+d_H\left(S_H\right)+\left(b+1\right)d_{F\left(G\right)}\left(S_G\right)$ 。

如果 $\left|V\left(F_G\left(h_j\right)\right)\cap S\right|=1$ ，其中 $1\le j\le y$ 。若 $y\ge 3$ ，则 $G{+}_{F}H$ 的一个S-Steiner树是由边 $\left({\displaystyle \underset{j=y+1}{\overset{r}{\cup }}E}\left(T\left(h_j\right)\right)\right)\cup E\left(T\left(g_{i_1}\right)\right)\cup \left({\displaystyle \underset{j=1}{\overset{r}{\cup }}E}\left(u,T\left(h_j\right)\right)\right)$ 组成，由b的定义，可得 $b=r-3$ 。若 $y=1$ 或者 $y=2$ ，则 $G{+}_{F}H$ 的一个S-Steiner树是由边 $\left({\displaystyle \underset{j=2}{\overset{r}{\cup }}E}\left(T\left(h_j\right)\right)\right)\cup E\left(T\left(g_{i_1}\right)\right)\cup \left({\displaystyle \underset{j=1}{\overset{r}{\cup }}E}\left(u,T\left(h_j\right)\right)\right)$ 组成，由b的定义可得 $b=r-1$ 或 $b=r-2$ 。即 $d_{G{+}_{F}H}\left(S\right)\le r+d_H\left(S_H\right)+\left(b+1\right)d_{F\left(G\right)}\left(S_G\right)$ 。

情况3. 存在两个顶点 $\left(g_{i_p},h_{j_p}\right)\in V\left(G\right)$ ， $\left(g_{i_q},h_{j_q}\right)\in E\left(G\right)$ ，其中顶点 $\left(g_{i_p},h_{j_p}\right),\left(g_{i_q},h_{j_q}\right)\in S$ ， $3\le k\le mn+m\epsilon$ 。

每一个 $F_G\left(h_j\right)$ $\left(1\le j\le r\right)$ 都有与之相对应的Steiner树 $T\left(h_j\right)$ 。因此 $T\left(h_j\right)$ $\left(1\le j\le r\right)$ 是一个大小为 $d_{F_G}\left(S_G\right)$ 且包含 $F_G\left(h_j\right)$ 的顶点 $\left\{\left(g_{i_1},h_j\right),\left(g_{i_2},h_j\right),\cdots ,\left(g_{i_p},h_j\right),\cdots ,\left(g_{i_s},h_j\right),\left(g_{i_{s+1}},h_j\right),\cdots ,\left(g_{i_k},h_j\right)\right\}$ 的Steiner树。同样地，H有一个大小为 $d_H\left(S_H\right)$ 的 $S_H$ -Steiner树，因此 $T\left(g_{i_p}\right)$ 是一个大小为 $d_H\left(S_H\right)$ 且包含 $H\left(g_{i_p}\right)$ 中顶点 $\left\{\left(g_{i_p},h_{j_1}\right),\left(g_{i_p},h_{j_2}\right),\cdots ,\left(g_{i_p},h_r\right)\right\}$ 的Steiner树(见图3)。

Figure 3. S contains two types of vertices

图3. S中包含两种类型的顶点

情况3的连接方式与情况1类似，即可证 $d_{G{+}_{F}H}\left(S\right)\le d_H\left(S_H\right)+\left(b+1\right)d_{F\left(G\right)}\left(S_G\right)$ 。

现在来考虑下界。令 $S=\left\{\left(g_{i_1},h_{j_1}\right),\left(g_{i_2},h_{j_2}\right),\cdots ,\left(g_{i_k},h_{j_k}\right)\right\}\subseteq V\left(G{+}_{F}H\right)$ ，其中 $S_G=\left\{g_{i_1},g_{i_2},\cdots ,g_{i_k}\right\}\subseteq V\left(F\left(G\right)\right)$ ， $S_H=\left\{h_{j_1},h_{j_2},\cdots ,h_{j_k}\right\}\subseteq V\left(H\right)$ 。根据图 $G{+}_{F}H$ 的结构特征，显然 $d_{G{+}_{F}H}\left(S\right)\ge d_{F\left(G\right)}\left(S_G\right))+d_H\left(S_H\right)$ 。

推论3 G和H是两个连通图，且 $k\ge 3$ 是一个整数。令 $S=\left\{\left(g_{i_1},h_{j_1}\right),\left(g_{i_2},h_{j_2}\right),\cdots ,\left(g_{i_k},h_{j_k}\right)\right\}$ 是 $G{+}_{F}H$ 的一个顶点各不相同的集合。令 $S_G=\left\{g_{i_1},g_{i_2},\cdots ,g_{i_k}\right\}$ ， $S_H=\left\{h_{j_1},h_{j_2},\cdots ,h_{j_k}\right\}$ 。如果 $S_G\subseteq E\left(G\right)$ 且 $g_{i_1}=g_{i_2}=\cdots =g_{i_k}$ ，则 $d_{G{+}_{F}H}\left(S\right)=r+d_H\left(S_H\right)$ ，其中F代表 $S,R,Q$ 和T中的其中一个。 $H\left(g\right)$ $\left(g\in F\left(G\right)\right)$ 是H的一个复制，且 $\left|V\left(H\left(g\right)\right)\cap S\right|=r$ 。

推论4 令G和H是两个阶数分别为 $n,m$ 的连通图，令 $k,m,n$ 是三个整数，并且 $3\le k\le m\left(n+\epsilon \right)$ ( $\epsilon$ 是图G的边数)， $n\le m\le n+\epsilon$ 。假设 $H\left(g\right)$ $\left(g\in F\left(G\right)\right)$ 是H的一个复制， 可以知道 $\left|V\left(H\left(g\right)\right)\cap S\right|=r$ ，F-sum图的Steiner直径如下

如果 $k\le m$ ，则

$\begin{array}{l}sdia{m}_k\left(F\left(G\right)\right)+sdia{m}_k\left(H\right)\le sdia{m}_k\left(G{+}_{F}H\right)\\ \le r+sdia{m}_k\left(F\left(G\right)\right)+sdia{m}_k\left(H\right)+\left(k-3\right)\min \left\{sdia{m}_k\left(F\left(G\right)\right),sdia{m}_k\left(H\right)\right\},\end{array}$

如果 $m<k\le mn$ ，则

$\begin{array}{l}sdia{m}_k\left(F\left(G\right)\right)+m-1\le sdia{m}_k\left(G{+}_{F}H\right)\\ \le r+sdia{m}_k\left(F\left(G\right)\right)+m-1+\left(k-3\right)\min \left\{sdia{m}_k\left(F\left(G\right)\right),m-1\right\},\end{array}$

如果 $mn<k\le m\left(n+\epsilon \right)$ ，则

$n+m+\epsilon -2\le sdia{m}_k\left(G{+}_{F}H\right)\le n+\epsilon -1+\left(k-2\right)\left(m-1\right)$ 。

3. 结论

本文基于先前建立的关于图乘积的Steiner距离的结果，推广并证明了两个图的corona积和cluster积的Steiner半径，并用来自两个原始图的参数来表示它们。然后，在F-sum图中给出了Steiner距离的界，这反过来又有助于界定F-sum图的Steiner直径。以上得到的主要定理也可以应用于特殊图，并提供了简单的推论。

基金项目

国家自然科学基金项目(12201273)；浙江省自然科学基金项目(LY21A010002)。

NOTES

^*通讯作者。