一类图和偶圈的直积的超边连通度 The Super Edge-Connectivity of Direct Product of a Family of Graph and an Even Cycle

doi:10.12677/AAM.2024.132052

Advances in Applied Mathematics
Vol. 13 No. 02 ( 2024 ), Article ID: 81261 , 8 pages
10.12677/AAM.2024.132052

●How to Cite this Article

一类图和偶圈的直积的超边连通度

郭思佳，赵爽^*，王健

太原理工大学数学学院，山西晋中

收稿日期：2024年1月21日；录用日期：2024年2月19日；发布日期：2024年2月26日

摘要

连通图G的超边连通度是指使得图G不连通且每个连通分支没有孤立点要删除的最少的边数，用 $λ^{'} (G)$ 表示。图G和H的直积，定义为 $G \times H$ ，是顶点集为 $V (G \times H) = V (G) \times V (H)$ 的图，其中两个顶点 $(u_{1}, v_{1})$ 和 $(u_{2}, v_{2})$ 在 $G \times H$ 相邻当且仅当 $u_{1} u_{2} \in E (G)$ 且 $v_{1} v_{2} \in E (H)$ 。马天龙等人证明了G和完全图 $K_{n}$ 的直积的超边连通度。本文证明了当 $n \geq 4$ 且 $n$ 为偶数时，一类图G和圈 $C_{n}$ 的直积的超边连通度为 $λ^{'} (G \times C_{n}) = m i n {2 n λ^{'} (G), \underset{x y \in E (G)}{m i n} {(d e g_{G} (x) + d e g_{G} (y)) \times 2 - 2}}$ 。

关键词

边连通度，超边连通度，直积

Sijia Guo, Shuang Zhao^*, Jian Wang

School of Mathematics, Taiyuan University of Technology, Jinzhong Shanxi

Received: Jan. 21^st, 2024; accepted: Feb. 19^th, 2024; published: Feb. 26^th, 2024

The Super Edge-Connectivity of Direct Product of a Family of Graph and an Even Cycle

ABSTRACT

The super edge-connectivity of a connected graph G, denoted by $λ^{'} (G)$ , is the minimum number of edges whose deletion disconnects the graph such that each connected component has no isolated vertices. The direct product of graphs G and H, denoted by $G \times H$ , is the graph with vertex set $V (G \times H) = V (G) \times V (H)$ , where two vertices $(u_{1}, v_{1})$ and $(u_{2}, v_{2})$ are adjacent in $G \times H$ if and only if $u_{1} u_{2} \in E (G)$ and $v_{1} v_{2} \in E (H)$ . Tianlong Ma et al. proved the super edge-connectivity of the direct product of G and complete graph. In this paper, it is proved that $λ^{'} (G \times C_{n}) = m i n {2 n λ^{'} (G), \underset{x y \in E (G)}{m i n} {(d e g_{G} (x) + d e g_{G} (y)) \times 2 - 2}}$ for a family of a graph G, where $n \geq 4$ and n is even.

Keywords:Edge-Connectivity, Super Edge-Connectivity, Direct Product

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

圈 $C_{n}$ 的点集为 $V (C_{n}) = ℤ_{n} = {0, 1, \dots, n - 1}$ ，其中点i与点 $i + 1$ 相邻。 $G = (V, E)$ 是无向，有限阶的简单图。 $| G |$ 表示G的顶点数。对于G的任意一点u， $N_{G} (u)$ 是指G中与u相邻的点集， $\deg_{G} (u)$ 是指G中与u关联的边的数目。对于G中的任意一条边 $e = u v$ ，e的边度定义为 $ξ_{G} (e) = \deg_{G} (u) + \deg_{G} (v) - 2$ 。G的最小边度 $ξ (G)$ 定义为 $\min {ξ (e) : e \in E (G)}$ 。G的最小度 $δ (G)$ 定义为 $\min {\deg_{G} (u) : u \in V (G)}$ 。G的两个不交的非空集合A和B， $[A, B]$ 表示一个端点在A且另一个端点在B的边的集合。对于任意集合 $S \subseteq E (G)$ ， $G - S$ 表示从G中删掉S中所有边得到的图。对于任意的连通图G，如果 $G - S$ 是不连通的，则S是G的一个边割。如果 $G - S$ 没有孤立点，则边割S是一个超边割。

定义1.1：设G是一个连通图，其超边连通度 $λ^{'} (G)$ 的定义为：

$λ^{'} (G) = \min {| S | : S \subseteq E (G)}$ ，其中S是G的超边割；

如果超边连通度不存在，则 $λ^{'} (G) = + \infty$ 。

Esfahanian和Hakimi [1] 在1988年引入了超边连通度的概念，并证明出如果G不是K₃也不是 $K_{1, n - 1}$ 时，则 $λ (G) \leq λ^{'} (G) \leq ξ (G)$ 。

定义1.2：设G和H是两个无向图，图G和H的直积 $G \times H$ ，是顶点集为 $V (G \times H) = V (G) \times V (H)$ 的图，其中两个顶点 $(u_{1}, v_{1})$ 和 $(u_{2}, v_{2})$ 在 $G \times H$ 相邻当且仅当 $u_{1} u_{2} \in E (G)$ 且 $v_{1} v_{2} \in E (H)$ 。

Weichsel [2] 证明了两个非平凡图的直积图是连通的当且仅当这两个图都是连通的，且至少有一个不是二部图。Brešar和Špacapan [3] 得到了图 $G \times H$ 的边连通度的上界和下界。Cao，Brglez，Špacapan和Vumar在 [4] 中确定了非平凡图与完全图的直积的边连通度。Špacapan [5] 不仅得到了两个图的直积的边连通度，而且刻画了这个直积图中最小边割的结构。王伟和严志丹 [6] 确定了G与K₂的直积的点连通度。杨超 [7] 得到了非平凡图G与K₂的直积的边连通度。马天龙，王金玲和张明祖 [8] 得到了当 $n \geq 3$ 时，非平凡图与完全图K_n的直积的超边连通度。Sonawane和Borse [9] 得到了当G是二部图或C是偶圈时， $G \times C$ 的点连通度。

定义1.3：对于G中的任意一点 $u_{i}$ ， $G \times C_{n}$ 中关于 $u_{i}$ 的 $C_{n}$ 层的定义如下：

$C_{n}^{u_{i}} = {(u_{i}, j) \in V (G) \times V (C_{n}) : j \in V (C_{n})}$ 。

本文主要研究当 $n \geq 4$ 且n为偶数时，满足以下条件的非平凡图G与偶圈 $C_{n}$ 的直积的超边连通度：

1) $| G | = n$ ；2) G的任意两点间都存在长度为2的路。

2. 主要结论及其证明

我们首先给出主要结论的证明中所需要的引理。

引理2.1 [10] ：若G是一个连通图，则

$λ^{'} (G \times C_{n}) \leq \min {2 n λ^{'} (G), \min_{x y \in E (G)} {(\deg_{G} (x) + \deg_{G} (y)) \times 2 - 2}}$ ，其中 $n \geq 3$ 。

引理2.2 [10] ：对于任意的连通图G，设 $S \subset E (G \times C_{n})$ 是 $G \times C_{n}$ 的一个超边割，设 $C_{1}, C_{2}, \dots, C_{r} (r \geq 2)$ 为 $G \times C_{n} - S$ 的若干个连通分支。对于G中的任意一点 $u_{i}$ ，如果都存在一个连通分支 $C_{f}$ ，使得 $C_{n}^{u_{i}} \subseteq C_{f}$ ，那么 $| S | \geq 2 n λ^{'} (G)$ 。

引理2.3 [10] ：对于阶为n的连通图G，设 $S \subset E (G \times C_{n})$ 是 $G \times C_{n}$ 的一个最小超边割且 $| S | < 2 n λ^{'} (G)$ ，设C₁和C₂为 $G \times C_{n} - S$ 的两个连通分支，则在G中存在一点 $u_{i}$ ，使得 $C_{n}^{u_{i}} \cap C_{1} \neq \emptyset$ 且 $C_{n}^{u_{i}} \cap C_{2} \neq \emptyset$ 。此外，若 $u_{i}$ 在G中的每一个邻点 $u_{j}$ 都满足 $C_{n}^{u_{j}} \subset C_{1}$ 或 $C_{n}^{u_{j}} \subset C_{2}$ ，则 $| S | > \min_{x y \in E (G)} {(\deg_{G} (x) + \deg_{G} (y)) \times 2 - 2}$ 。

引理2.4 [11] ：设F和H为图G中两个不交的子图，使得F和H不连通所要删掉的最少边数等于F和H间边不交路的最大条数。

设 $S \subset E (G \times C_{n})$ 是 $G \times C_{n}$ 的一个最小超边割，设C₁和C₂为 $G \times C_{n} - S$ 的两个连通分支，由上述引理可知， $| S |$ 不小于连接C₁和C₂中的点的边不交路的最大条数。接下来的证明我们使用该方法。

定理2.5：设G是阶为n的非二部连通图，若G中任意两点都有长为2的路，则

$λ^{'} (G \times C_{n}) = \min {2 n λ^{'} (G), \min_{x y \in E (G)} {(\deg_{G} (x) + \deg_{G} (y)) \times 2 - 2}}$ ，其中 $n \geq 4$ 且n是偶数。

证明：由引理2.1可知，只需证 $λ^{'} (G \times C_{n}) \geq \min {2 n λ^{'} (G), \min_{x y \in E (G)} {(\deg_{G} (x) + \deg_{G} (y)) \times 2 - 2}}$ 。

设 $S \subset E (G \times C_{n})$ 是 $G \times C_{n}$ 的一个最小超边割，设C₁和C₂为 $G \times C_{n} - S$ 的两个连通分支，使用反证法，假设 $| S | < 2 n λ^{'} (G)$ 且 $| S | < \min_{x y \in E (G)} {(\deg_{G} (x) + \deg_{G} (y)) \times 2 - 2}$ ，由引理2.3可知，在G中存在一点 $u_{i}$ ，使得 $C_{n}^{u_{i}} \cap C_{1} \neq \emptyset$ 且 $C_{n}^{u_{i}} \cap C_{2} \neq \emptyset$ 。接下来我们分两种情况进行讨论：

情况1. 在G中存在一个 $u_{i}$ 的邻居 $u_{j}$ ，使得 $C_{n}^{u_{j}} \cap C_{1} \neq \emptyset$ 且 $C_{n}^{u_{j}} \cap C_{2} \neq \emptyset$ 。

由于G中的任意两点都有长为2的路，则 $u_{i}$ 和 $u_{j}$ 至少有一个公共的邻点，不妨设该点为 $u_{a}$ 。假设 $N_{G} (u_{i}) = {u_{j} (= u_{h_{1}}), u_{a} (= u_{h_{2}}), \dots, u_{h_{k}}}$ 且 $N_{G} (u_{j}) = {u_{i} (= u_{g_{1}}), u_{a} (= u_{g_{2}}), \dots, u_{g_{l}}}$ ，其中 $k = \deg_{G} (u_{i})$ 且 $l = \deg_{G} (u_{j})$ 。

当n为偶数时，C_n是一个二部图，则C_n是2-点可着色的。对于G中的任意一点 $u_{i}$ ， $C_{n}^{u_{i}}$ 层中点的颜色保留C_n中点的颜色。

子情况1.1. $C_{n}^{u_{i}} \cap C_{1}$ 或 $C_{n}^{u_{i}} \cap C_{2}$ 中点的颜色不同，不妨设 $C_{n}^{u_{i}} \cap C_{1}$ 中点的颜色不同，则在 $C_{n}^{u_{i}} \cap C_{1}$ 中存在一点与 $C_{n}^{u_{i}} \cap C_{2}$ 中某一点的颜色相同，设这两点分别为 $(u_{i}, x_{1})$ 和 $(u_{i}, y_{1})$ 。考虑以下路径：

$P_{1} : = (u_{i}, x_{1}) \to (u_{h_{t}}, x_{1} - 1) \to \dots \to (u_{h_{t}}, y_{1} + 1) \to (u_{i}, y_{1})$ ， $t \in {1, \dots, k}$

$P_{2} : = (u_{i}, x_{1}) \to (u_{h_{t}}, x_{1} + 1) \to \dots \to (u_{h_{t}}, y_{1} - 1) \to (u_{i}, y_{1})$ ， $t \in {1, \dots, k}$

P₁和P₂这种结构的路都有k条。

子情况1.1.1. $C_{n}^{u_{j}} \cap C_{1}$ 或 $C_{n}^{u_{j}} \cap C_{2}$ 中点的颜色不同，不妨设 $C_{n}^{u_{j}} \cap C_{1}$ 中点的颜色不同，则在 $C_{n}^{u_{j}} \cap C_{1}$ 中存在一点与 $C_{n}^{u_{j}} \cap C_{2}$ 中某一点的颜色相同，设这两点分别为 $(u_{j}, x_{2})$ 和 $(u_{j}, y_{2})$ 。考虑以下路径：

$P_{3} : = (u_{j}, x_{2}) \to (u_{g_{t}}, x_{2} - 1) \to \dots \to (u_{g_{t}}, y_{2} + 1) \to (u_{j}, y_{2})$ ， $t \in {2, \dots, l}$

$P_{4} : = (u_{j}, x_{2}) \to (u_{g_{t}}, x_{2} + 1) \to \dots \to (u_{g_{t}}, y_{2} - 1) \to (u_{j}, y_{2})$ ， $t \in {2, \dots, l}$

P₃和P₄这种结构的路都有 $(l - 1)$ 条。

P₁-P₄为边不交的路，于是

$\begin{matrix} | S | \geq k + k + l - 1 + l - 1 = 2 (k + l) - 2 \\ = 2 (\deg_{G} (u_{i}) + \deg_{G} (u_{j})) - 2 \\ \geq \min_{x y \in E (G)} {(\deg_{G} (x) + \deg_{G} (y)) \times 2 - 2} \end{matrix}$ ，

产生矛盾。

子情况1.1.2. $C_{n}^{u_{j}} \cap C_{1}$ 中点的颜色相同且 $C_{n}^{u_{j}} \cap C_{2}$ 中点的颜色相同，则 $C_{n}^{u_{j}}$ 中的点被平均分配到两个连通分支中，每个连通分支都有n/2个点。考虑以下路径：

$P_{5} : = (u_{j}, d) \to (u_{i}, d + 1) \to (u_{a}, d) \to (u_{j}, d + 1)$ ， $d \in {0, 1, \dots, n - 1}$

$P_{6} : = (u_{j}, d) \to (u_{i}, d - 1) \to (u_{a}, d) \to (u_{j}, d - 1)$ ， $d \in {0, 1, \dots, n - 1}$

P₅和P₆这种结构的路都有n条。

删除P₁和P₂中 $u_{h_{t}} = u_{j}$ 和 $u_{h_{t}} = u_{a}$ 的路，剩下的P₁、P₂、P₅和P₆均为内部边不交的路，于是

$\begin{matrix} | S | \geq k - 2 + k - 2 + n + n = 2 (k + n - 1) - 2 \\ \geq 2 (\deg_{G} (u_{i}) + \deg_{G} (u_{j})) - 2 \\ \geq \min_{x y \in E (G)} {(\deg_{G} (x) + \deg_{G} (y)) \times 2 - 2} \end{matrix}$ ，

产生矛盾。

子情况1.2. $C_{n}^{u_{i}} \cap C_{1}$ 中点的颜色相同且 $C_{n}^{u_{i}} \cap C_{2}$ 中点的颜色相同，则 $C_{n}^{u_{i}}$ 中的点被平均分配到两个连通分支中，每个连通分支都有n/2个点。

子情况1.2.1. $C_{n}^{u_{j}} \cap C_{1}$ 或 $C_{n}^{u_{j}} \cap C_{2}$ 中点的颜色不同。

该情况与子情况1.1.2类似，故也会产生矛盾。

子情况1.2.2. $C_{n}^{u_{j}} \cap C_{1}$ 中点的颜色相同且 $C_{n}^{u_{j}} \cap C_{2}$ 中点的颜色相同，则 $C_{n}^{u_{i}}$ 中的点被平均分配到两个连通分支中，每个连通分支都有n/2个点。考虑以下路径：

$P_{1} : = (u_{j}, d) \to (u_{i}, d + 1) \to (u_{a}, d) \to (u_{j}, d + 1)$ ， $d \in {0, 1, \dots, n - 1}$

$P_{2} : = (u_{j}, d) \to (u_{i}, d - 1) \to (u_{a}, d) \to (u_{j}, d - 1)$ ， $d \in {0, 1, \dots, n - 1}$

P₁和P₂这种结构的路都有n条。

当 $δ (G) = 1$ 时，不妨设 $\deg (u_{d}) = 1$ ，设 $u_{d}$ 的一个邻居为 $u_{h}$ 。P₁-P₂为边不交的路，于是

$\begin{matrix} | S | \geq n + 1 + n + 1 - 2 = 2 (n + 1) - 2 \\ > 2 (\deg (u_{h}) + \deg (u_{d})) - 2 \\ \geq \min_{x y \in E (G)} {(\deg_{G} (x) + \deg_{G} (y)) \times 2 - 2} \end{matrix}$ ，

产生矛盾。

当 $δ (G) = 2$ 时，不妨设 $\deg (u_{d}) = 2$ ，设 $u_{d}$ 的一个邻居为 $u_{h}$ 。P₁-P₂为边不交的路，于是

$\begin{matrix} | S | \geq n - 1 + 2 + n - 1 + 2 - 2 = 2 (n - 1 + 2) - 2 \\ \geq 2 (\deg (u_{h}) + \deg (u_{d})) - 2 \\ \geq \min_{x y \in E (G)} {(\deg_{G} (x) + \deg_{G} (y)) \times 2 - 2} \end{matrix}$ ，

产生矛盾。

当 $δ (G) \geq 3$ 且 $C_{n}^{u_{i}} \cap C_{1}$ 与 $C_{n}^{u_{j}} \cap C_{1}$ 中点的颜色不同时，不妨设 $u_{b}$ 和 $u_{c}$ 分别为 $u_{i}$ 和 $u_{j}$ 的邻点，接下来的证明分两种情况讨论：

1) 若 $u_{i}$ 和 $u_{j}$ 至少存在两个公共邻点，不妨设 $u_{b} = u_{c}$ ，如图1所示，考虑以下路径：

$P_{3} : = (u_{i}, d) \to (u_{b}, d + 1) \to (u_{j}, d)$ ， $d \in {0, 1, \dots, n - 1}$

$P_{4} : = (u_{i}, d) \to (u_{b}, d - 1) \to (u_{j}, d)$ ， $d \in {0, 1, \dots, n - 1}$

P₃和P₄这种结构的路都有n条。

Figure 1. $u_{b} = u_{c}$

图1. $u_{b} = u_{c}$

2) 若 $u_{i}$ 和 $u_{j}$ 只存在一个公共邻点，则 $u_{b} \neq u_{c}$ 。由于G中任意两点都有长为2的路，设 $u_{b}$ 到 $u_{c}$ 的一条长为2的路为 $(u_{b}, u_{d}, u_{c})$ ，其中 $u_{d} \neq u_{j}$ 且 $u_{d} \neq u_{i}$ ，否则与 $u_{i}$ 和 $u_{j}$ 只存在一个公共邻点矛盾，如图2所示。考虑以下路径：

$P_{5} : = (u_{i}, d) \to (u_{b}, d + 1) \to (u_{d}, d) \to (u_{c}, d + 1) \to (u_{j}, d)$ ， $d \in {0, 1, \dots, n - 1}$

$P_{6} : = (u_{i}, d) \to (u_{b}, d - 1) \to (u_{d}, d) \to (u_{c}, d - 1) \to (u_{j}, d)$ ， $d \in {0, 1, \dots, n - 1}$

P₅和P₆这种结构的路都有n条。

Figure 2. $u_{b} \neq u_{c}$

图2. $u_{b} \neq u_{c}$

上述两种情况出现的路与P₁、P₂均为边不交的路。因此这两种情况，都有

$| S | \geq n + n + n + n > \min_{x y \in E (G)} {(\deg_{G} (x) + \deg_{G} (y)) \times 2 - 2}$ ，产生矛盾。

当 $δ (G) \geq 3$ 且 $C_{n}^{u_{i}} \cap C_{1}$ 与 $C_{n}^{u_{j}} \cap C_{1}$ 中点的颜色相同时，考虑以下路径：

$P_{1} : = (u_{i}, d) \to (u_{j}, d + 1)$ ， $d \in {0, 1, \dots, n - 1}$

$P_{2} : = (u_{i}, d) \to (u_{j}, d - 1)$ ， $d \in {0, 1, \dots, n - 1}$

设 $u_{a}$ 的另一邻点为 $u_{f}$ ， $u_{f}$ 、 $u_{b}$ 和 $u_{c}$ 三者之间的关系主要分以下两种情况讨论：

1) 当 $u_{b} \neq u_{f}$ 且 $u_{f} \neq u_{c}$ 时。设 $u_{b}$ 到 $u_{f}$ 的一条2长的路为 $(u_{b}, u_{h}, u_{f})$ 。

当 $u_{h} = u_{a}$ 时，如图3所示，考虑以下路径：

$P_{3} : = (u_{i}, d) \to (u_{b}, d + 1) \to (u_{a}, d) \to (u_{j}, d + 1)$ ， $d \in {0, 1, \dots, n - 1}$

$P_{4} : = (u_{i}, d) \to (u_{b}, d - 1) \to (u_{a}, d) \to (u_{j}, d - 1)$ ， $d \in {0, 1, \dots, n - 1}$

P₃和P₄这种结构的路都有n条。

Figure 3. $u_{h} = u_{a}$

图3. $u_{h} = u_{a}$

当 $u_{h} = u_{j}$ 时，如图4所示，考虑以下路径：

$P_{5} : = (u_{i}, d) \to (u_{a}, d + 1) \to (u_{f}, d) \to (u_{j}, d + 1)$ ， $d \in {0, 1, \dots, n - 1}$

$P_{6} : = (u_{i}, d) \to (u_{a}, d - 1) \to (u_{f}, d) \to (u_{j}, d - 1)$ ， $d \in {0, 1, \dots, n - 1}$

P₅和P₆这种结构的路都有n条。

当 $u_{h} = u_{i}$ 时，如图5所示，考虑以下路径：

$P_{7} : = (u_{i}, d) \to (u_{f}, d + 1) \to (u_{a}, d) \to (u_{j}, d + 1)$ ， $d \in {0, 1, \dots, n - 1}$

$P_{8} : = (u_{i}, d) \to (u_{f}, d - 1) \to (u_{a}, d) \to (u_{j}, d - 1)$ ， $d \in {0, 1, \dots, n - 1}$

P₇和P₈这种结构的路都有n条。

否则，如图6所示，考虑以下路径：

$P_{9} : = (u_{i}, d) \to (u_{b}, d + 1) \to (u_{h}, d) \to (u_{f}, d + 1) \to (u_{a}, d) \to (u_{j}, d + 1)$ ， $d \in {0, 1, \dots, n - 1}$

$P_{10} : = (u_{i}, d) \to (u_{b}, d - 1) \to (u_{h}, d) \to (u_{f}, d - 1) \to (u_{a}, d) \to (u_{j}, d - 1)$ ， $d \in {0, 1, \dots, n - 1}$

P₉和P₁₀这种结构的路都有n条。

P₁、P₂与P₃、P₄或P₅、P₆或P₇、P₈或P₉、P₁₀为边不交的路，因此上述的所有情况，都有

$| S | \geq n + n + n + n > \min_{x y \in E (G)} {(\deg_{G} (x) + \deg_{G} (y)) \times 2 - 2}$ ，产生矛盾。

Figure 4. $u_{h} = u_{j}$

图4. $u_{h} = u_{j}$

Figure 5. $u_{h} = u_{i}$

图5. $u_{h} = u_{i}$

Figure 6. $u_{h} \notin {u_{a}, u_{i}, u_{j}}$

图6. $u_{h} \notin {u_{a}, u_{i}, u_{j}}$

2) 当 $u_{b} = u_{f}$ 或 $u_{f} = u_{c}$ 时，若前者成立考虑P₃和P₄，否则，考虑P₅和P₆，故都会产生矛盾。

情况2. 对于 $u_{i}$ 的每一个邻居 $u_{j}$ ，都有 $C_{n}^{u_{j}} \subset C_{1}$ 或 $C_{n}^{u_{j}} \subset C_{2}$ 。

由引理2.3，可知 $| S | > \min_{x y \in E (G)} {(\deg_{G} (x) + \deg_{G} (y)) \times 2 - 2}$ ，产生矛盾。

3. 结论

本文主要通过寻找位于两个连通分支顶点间边不交路的方法，得到了同时满足(i) $| G | = n$ ，(ii) G的任意两点间都存在长度为2的路，这两种条件下的非二部连通图G与偶圈直积的超边连通度，即 $λ^{'} (G \times C_{n}) = \min {2 n λ^{'} (G), \min_{x y \in E (G)} {(\deg_{G} (x) + \deg_{G} (y)) \times 2 - 2}}$ 。新问题的解决往往伴随着很强的创新性。目前，一个图和圈直积的超边连通度这一问题并未完全解决，后续可以进一步研究。

基金项目

山西省青年科学研究项目(202103021223110)，太原理工大学青年科学基金项目(2022QN097)。

文章引用

郭思佳,赵爽,王健. 一类图和偶圈的直积的超边连通度
The Super Edge-Connectivity of Direct Product of a Family of Graph and an Even Cycle[J]. 应用数学进展, 2024, 13(02): 531-538. https://doi.org/10.12677/AAM.2024.132052

参考文献

1. Esfahanian, A.H. and Hakimi S.L. (1988) On Computing a Conditional Edge-Connectivity of a Graph. Information Processing Letters, 27, 195-199. https://doi.org/10.1016/0020-0190(88)90025-7

2. Weichsel, P.M. (1962) The Kronecker Product of Graphs. Proceedings of the American Mathematical Society, 13, 47-52. https://doi.org/10.1090/S0002-9939-1962-0133816-6

3. Brešar, B. and Špacapan, S. (2008) On the Connectivity of the Direct Product of Graphs. The Australasian Journal of Combinatorics, 41, 45-56.

4. Cao, X., Brglez, Š., Špacapan, S. and Vumar, S. (2011) On Edge Connectivity of Direct Products of Graphs. Information Processing Letters, 111, 899-902. https://doi.org/10.1016/j.ipl.2011.06.007

5. Špacapan, S. (2013) A Characterization of the Edge Connectivity of Direct Products of Graphs. Discrete Mathematics, 313, 1385-1393. https://doi.org/10.1016/j.disc.2013.02.011

6. Wang, W. and Yan, Z. (2012) Connectivity of Kronecker Products by k2. Applied Mathematics Letters, 25, 172-174. https://doi.org/10.1016/j.aml.2011.08.009

7. Yang, C. (2007) Connectivity and Fault-Diameter of Product Graphs. Ph.D. Thesis, University of Science and Technology of China, Hefei.

8. Ma, T.L., Wang, J.L. and Zhang, M.Z. (2019) The Restricted Edge-Connectivity of Kronecker Product Graphs. Parallel Processing Letters, 29, 1950012:1-1950012:7. https://doi.org/10.1142/S0129626419500129

9. Sonawane, A.V. and Borse, Y.M. (2021) Connectivity of the Tensor Product of a Graph and a Cycle. Journal of the Ramanujan Mathematical Society, 36, 325-330.

10. Guo, S.J. and Zhao, S. The Super Edge-Connectivity of Direct Product of a Graph and a Cycle. (Submitted)

11. Dirac, G. (1960) Généralisations du théoréme de menger. C.R. Acad. Sci, 250, 4252-4253.

NOTES

^*通讯作者。

期刊菜单