The generalized 4-connectivity of bubble-sort graphs
- 分享到:
摘要：
S⊆V(G)是G的一个顶点集且|S|≥k,其中2≤k≤n.连接S的树T叫作斯坦纳树.两棵斯坦纳树T 1和T 2称为内部不交的,当且仅当它们满足E(T1)∩E(T2)=Φ和V(T1)∩V(T2)=S.令κG(S)是G内部不交的斯坦纳树的最大数目,κk(G)=min{κG(S)∶S⊆V(G),|S|=k}定义为G的广义k-连通度.很显然,当|S|=2时,广义2-连通度κ2(G)就是经典连通度κ(G).因此广义连通度是经典连通度的推广.主要讨论泡序图Bn的广义4-连通度κ4(Bn).得到的结论是当n3时,κ4(Bn)=n-2.
Let S⊆V(G)be a vertex set and|S|≥k for 2≤k≤n,a tree T is called an S-Steiner tree if T connects S.Two S-Steiner trees T1 and T2 are internally disjoint if E(T1)∩E(T2)=Φ and V(T1)∩V(T2)=S.LetκκG(S)be the maximum number of the internally disjoint S-Steiner trees.κk(G)=min{κG(S)∶S⊆V(G),|S|=k}is defined as the generalized k-connectivity of G.Obviously,when|S|=2,the generality 2-connectivityκ2(G)is the classical connectivityκ(G).Then the generality connectivity is a generalization of the classical connectivity.In this paper,we focus on the generality 4-connectivityκ4(B n)of the bubble-sort graph B n and get κ4(Bn)=n-2 when n≥3.
作者:
王艳玲 冯伟
Wang Yanling;Feng Wei(College of Mathematics and Information Science,Henan Normal University,Xinxiang 453007,China;College of Mathematics and Physics,Inner Mongolia Minzu University,Tongliao 028043,China)
机构地区:
betway官方app 数学与信息科学学院 内蒙古民族大学数理学院
出处:
《betway官方app 学报：自然科学版》 CAS 北大核心 2023年第1期47-53,共7页
Journal of Henan Normal University(Natural Science Edition)
基金:
内蒙古自然科学基金(2022LHMS01006) 2022年度自治区直属高校基本科研业务费项目(GXKY22156).
关键词:
广义4-连通度 内部不交 泡序图 路
generalized 4-connectivity internally disjoint bubble-sort graphs paths
分类号:
O157.5 [理学—基础数学]
