摘要
S⊆V(G)是G的一个顶点集且|S|≥k,其中2≤k≤n.连接S的树T叫作斯坦纳树.两棵斯坦纳树T 1和T 2称为内部不交的,当且仅当它们满足E(T_(1))∩E(T_(2))=Φ和V(T_(1))∩V(T_(2))=S.令κG(S)是G内部不交的斯坦纳树的最大数目,κ_(k)(G)=min{κ_(G)(S)∶S⊆V(G),|S|=k}定义为G的广义k-连通度.很显然,当|S|=2时,广义2-连通度κ_(2)(G)就是经典连通度κ(G).因此广义连通度是经典连通度的推广.主要讨论泡序图B_(n)的广义4-连通度κ_(4)(B_(n)).得到的结论是当n_(3)时,κ_(4)(B_(n))=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 T_(1) and T_(2) are internally disjoint if E(T_(1))∩E(T_(2))=Φ and V(T_(1))∩V(T_(2))=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)(B_(n))=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)
出处
《河南师范大学学报(自然科学版)》
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