Advances in Applied Mathematics
Vol.
11
No.
08
(
2022
), Article ID:
54495
,
6
pages
10.12677/AAM.2022.118563
若干有向卡氏积图类广义3-弧强连通度的 精确值
喻俊燃
绍兴文理学院,数理信息学院,浙江 绍兴
收稿日期:2022年7月5日;录用日期:2022年7月31日;发布日期:2022年8月9日
摘要
无向图G的广义k-边连通度的定义是1985年由Hager引入的,这个定义后来又被人们推广到有向图中,并相应定义了有向图中的广义k-弧强连通度。近年来,广义k-弧强连通度的研究得到了很多重要的结果。在本文中,我们给出了某些有向卡氏积图类的3-弧强连通度的精确值。
关键词
有向树连通度,笛卡尔乘积,树连通度
Precise Values for the Generalized 3-Arc-Connectivity of Cartesian Product of Some Digraph Classes
Junran Yu
Department of Mathematics, Shaoxing University, Shaoxing Zhejiang
Received: Jul. 5th, 2022; accepted: Jul. 31st, 2022; published: Aug. 9th, 2022
ABSTRACT
The definition of generalized k-edge connectivity of undirected graph G was introduced by Hager in 1985. This concept was extended to directed graph and the definition of generalized -arc- connectivity was proposed. In recent years, the study of generalized -arc-connectivity has achieved many important results. In this paper, we give precise values for the generalized 3-arc-connectivity of Cartesian product of some digraph classes.
Keywords:Directed Tree Connectivity, Cartesian Product, Tree Connectivity
Copyright © 2022 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
1. 引言
在未特别声明的情况下,本篇论文涉及到的图均指有限、无环的并且没有平行弧的简单有向图,未解释的符号及术语引自文献 [1] [2] 。
用 与 分别表示有向图D的顶点集与弧集,一个有向图D是对称的,如果它可以由将对应的无向底图的边替换为两个相反方向的弧得到,也即 。圈有向图有两种,若在有向图D中,对D中每对不同的顶点x的和y,xy或者yx在图D的弧集里,这样的具有n个顶点的圈有向图记为 。若在有向图D中,对D中每对不同的顶点x的和y,xy和yx均在图D的弧集里,这样的具有m个顶点的圈有向图记为 。
无向图 的广义k-连通度 的概念由Hager [3] 于1985年引入 。给定图G及其顶点子集 (S中至少含有2个顶点),当G中的子树T满足 时,称这个树T为一个S-斯坦纳树,或者简称其为S-树。当两个S-树 和 满足 并且 时,我们称 和 为内部不交的。广义局部连通度 [3] 定义为G中内部不交S-树的最大个数。进一步,我们定义广义k-连通度:
其中k满足 。当两个S-树 和 满足 时,我们称 和 为弧不交的。类似的,广义局部边连通度 定义为G中边不交S-树的最大个数。相应的,我们定义 为:
其中 为G中弧不交S-树的最大个数 [4] 。其他有关无向图树连通度的结果可参考 [5] 。
为了将广义连通度的概念推广到有向图上,Sun和Yeo引入了有向图的树连通度的概念 [6] ,给定是n阶有向图 及其k元顶点子集S ( )且根节点 。一棵有向 -斯坦纳树或者简称为 -树T是一颗根节点在 并且 的外向树。两个 -树 和 被称为弧不相交的,若 。两个弧不相交的 -树 和 被称为内部不相交,若 。定义 是D中内部不相交的 -树的最大数目。定义D的广义k-点强连通度为:
作为k-边连通度的自然对应,Sun和Yeo [6] 引入了广义k-弧强连通度的概念。给定n阶有向图 及其k元顶点子集S ( )。定义 为D中弧不相交的 -树的最大数目。D的广义k-弧强连通度定义为:
关于有向图树连通度极值结果,Sun研究了有向图树连通度相关的极值问题 [7] ,给出了极小广义 -点(弧)强连通有向图的定义:这类图的广义k-点(弧)强连通度至少为 ,但去掉任意一条弧后,广义k-点(弧)强连通度至多为 。并且在某些情形下对极小广义 -点(弧)强连通有向图分别进行了刻画。其他有关无向图树连通度的结果可参考综述文章 [8] 。
两个有向图G和H的卡氏积 是具有顶点集
和弧集
的有向图。
根据定义,我们可以证明G和H的卡氏积 是强连通的当且仅当G和H都是强连通的 [9] 。
令G和H是顶点集分别是 和 的有向图。我们用符号 来表示 中当 时由顶点集 生成的有向子图,并且用 来表示 中当 时由顶点集 生成的有向子图。容易看出, 并且 。具体例子见下图1。
Figure 1. G, H Cartesian products
图1. G和H的卡氏积
2. 主要结果
引理2.1. [4] 令D为一个n阶有向图,k为一个整数且 ,则
其中 是D的一个生成有向子图。
定理2.2. 对于任意给定的两个正整数n和m,我们有
证明:由引理2.1可知, ,故只需在卡氏积图 找出2颗弧不交的 -树 和 即可。
令 ,根据 在顶点子集中的分布情况,不难看出只需考虑 当 时分别在不同的 和 当中即可,其他的情形的讨论是类似的。不失一般性我们可以假设 。由于 和 都是强连通的,故 也是强连通的,根据已知事实任意强连通有向图的任意顶点都能做外(内)分支的根点,故不失一般性我们可以设x为根点,如下图2所示,我们可以得到两颗包含S的弧不交的 -树 和 ,它们的顶点集与弧集分别为:
Figure 2. , and their Cartesian products
图2. 和 的卡氏积图
容易看出 和 是弧不交的。从而有
证毕。 ¨
定理2.3. 对于任意给定的两个正整数n和m,我们有
Figure 3. , and their Cartesian products
图3. 和 的卡氏积图
证明:由引理2.1可知, ,故只需在卡氏积图 找出3颗弧不交的 -树 , 和 即可。
令 ,根据 在顶点子集中的分布情况,不难看出只需考虑 当 时分别在不同的 和 当中即可,其他的情形的讨论是类似的。不失一般性我们可以假设 。由于 和 都是强连通的,故 也是强连通的,根据已知事实任意强连通有向图的任意顶点都能做外(内)分支的根点,故不失一般性我们可以设x为根点,如上图3所示,我们可以得到3颗包含S的弧不交的 -树 , 和 ,它们的顶点集与弧集分别为:
容易看出 , 和 是弧不交的。从而有
证毕。 ¨
定理2.4. 对于任意给定的两个正整数n和m,我们有
Figure 4. , and their Cartesian products
图4. 和 的卡氏积图
证明:由引理2.1可知, ,故只需在卡氏积图 找出4颗弧不交的 -树 , , 和 即可。
令 ,根据 在顶点子集中的分布情况,不难看出只需考虑 当 时分别在不同的 和 当中即可,其他的情形的讨论是类似的。不失一般性我们可以假设 。由于 和 都是强连通的,故 也是强连通的,根据已知事实任意强连通有向图的任意顶点都能做外(内)分支的根点,故不失一般性我们可以设x为根点,如上图4所示,我们可以得到4颗包含S的弧不交的 -树 , , 和 ,它们的顶点集与弧集分别为:
容易看出 , , 和 是弧不交的。从而有
证毕。 ¨
3. 总结和展望
本文给出了若干有向卡氏积图类广义3-弧强连通度的精确值,即给出了 , , 。进一步,我们还可以研究其他有向卡氏积图类广义3-弧强连通度精确值,同时考虑在此情况下能否同时给出这些有向卡氏积图类广义3-点强连通度的精确值,例如 的精确值。除此之外,还可以研究这些有向卡氏积图类广义k-弧强连通度 随着k取值不同的变化规律,是否能给出一个统一的取值公式。
文章引用
喻俊燃. 若干有向卡氏积图类广义3-弧强连通度的精确值
Precise Values for the Generalized 3-Arc-Connectivity of Cartesian Product of Some Digraph Classes[J]. 应用数学进展, 2022, 11(08): 5356-5361. https://doi.org/10.12677/AAM.2022.118563
参考文献
- 1. Bang-Jensen, J. and Gutin, G. (2009) Digraphs: Theory, Algorithms and Applications. 2nd Edition, Springer, London. https://doi.org/10.1007/978-1-84800-998-1
- 2. Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer, Berlin.
- 3. Hager, M. (1985) Pendant Tree-Connectivity. Journal of Combinatorial Theory, Series B, 38,179-189. https://doi.org/10.1016/0095-8956(85)90083-8
- 4. Li, X., Mao, Y. and Sun, Y. (2014) On the Generalized (Edge-)Connectivity of Graphs. Australasian Journal of Combinatorics, 58, 304-319.
- 5. Li, X. and Mao, Y. (2016) Generalized Connectivity of Graphs. Springer, Switzerland. https://doi.org/10.1007/978-3-319-33828-6
- 6. Sun, Y. and Yeo, A. (2022) Directed Steiner Tree Packing and Directed Tree Connectivity. Journal of Graph Theory, 101, 1-21. https://doi.org/10.1002/jgt.22858
- 7. Sun, Y.F. (2022) Extremal Results for Directed Tree Connectivity. Bulletin of the Malaysian Mathematical Sciences Society, 45, 839-850. https://doi.org/10.1007/s40840-021-01237-1
- 8. Sun, Y. (2022) Steiner Type Packing Problems in Di-graphs: A Survey, arXiv:2206.12092v1.
- 9. Hammack, R.H. (2018) Digraphs Products. In: Bang-Jensen, J. and Gutin, G., Eds., Classes of Directed Graphs, Springer, London. https://doi.org/10.1007/978-3-319-71840-8_10