泡序圖的廣義4-連通度

3 結 論

泡序圖有許多吸引研究者的性質.本文證明了當n3時，κ4（Bn）=n-2，即，在Bn中有至少（n-2）棵內部不交的斯坦納樹連接任意4個頂點.需要說明的是，那些內部不交的斯坦納樹是通過構造得到的，因此不是唯一存在的，Bn中還可能存在其他形式的內部不交斯坦納樹.隨后，作者會尋求Bn的廣義k-連通度中更一般的k.

參 考 文 獻

［1］ "WHITNEY H.Congruent graphs and the connectivity of graphs［J］.American Journal of Mathematics，1932，54（1）：150-168.

［2］HARARY F.Conditional connectivity［J］.Networks，1983，13（3）：347-357.

［3］FBREGA J，FIOL M A.On the extraconnectivity of grphs［J］.Discrete Mathematics，1996，155：49-57.

［4］LATIFI S，HEGDE M，NARAGHI-POUR M.Conditional connectivity measures for large multiprocessor systems［J］.IEEE Transactions on Computers，1994，43（2）：218-222.

［5］MENGER K.Zur allgemeinen kurventheorie［J］.Fundamenta Mathematicae，1927，10：96-115.

［6］LIN C-K，ZHANG L，FAN J，et al.Structure connectivity and substructure connectivity of hypercubes［J］.Theoretical Computer Science，2016，634：97-107.

［7］LI M，ZHANG S，LI R，et al.Structure fault tolerance of k-ary n-cube networks［J］.Theoretical Computer Science，2019，795：213-218.

［8］XU M，JING J.The connectivity and super connectivity of bubble-sort graph［J］.Acta Mathematicae Applicatae Sinica-Chinese，2012，35（5）：789-794.

［9］WANG S，WANG Z，WANG M.The 2-extra connectivity and 2-extra diagnosability of bubble-sort star graph networks［J］.The Computer Journal，2016，59（12）：1839-1856.

［10］WANG Y，WANG S.The 3-good-neighbor connectivity of modified bubble-sort graphs［J］.Mathematical Problems in Engineering，2020，2020：1-18.

［11］王世英，楊婕，馬曉蕾.修正泡型圖的條件匹配排除［J］.河南師范大學學報（自然科學版），2021，49（1）：1-9.

WANG S Y，YANG J，MA X L.Conditional matching preclusion of the modified bubble-sort graph［J］.Journal of Henan Normal University（Natural Science Edition），2021，49（1）：1-9.

［12］CHARTRAND G，KAPOOR S F，LESNIAK L，LICK D R.Generalized connectivity in graphs［J］.Bulletin Bombay Math Colloq，1984，2：1-6.

［13］LI S，LI X，ZHOU W.Sharp bounds for the generalized connectivity κ3（G）［J］.Discrete Mathematics，2010，310：2147-2163.

［14］ZHAO S，HAO R，WU J.The generalized 3-connectivity of some regular networks［J］.The Journal of Parallel and Distributed Computing，2019，133：18-20.

［15］LI S，TU J，YU C.The generalized 3-connectivity of star graphs and bubble-sort graphs［J］.Applied Mathematics and Computation，2016，274：41-46.

［16］LI S，SHI Y，TU J.The generalized 3-connectivity of Cayley graphs on symmetric groups generated by trees and cycles［J］.Graphs and Combinatorics，2017，33：1195-1209.

［17］LIN S，ZHANG Q.The generalized 4-connectivity of hypercubes［J］.Discrete Applied Mathematics，2017，220：60-67.

［18］ZHAO S，HAO R，WU J.The generalized 4-connectivity of hierarchical cubic networks［J］.Discrete Applied Mathematics，2021，289：194-206.

［19］ZHAO S，HAO R.The generalized 4-connectivity of exchanged hypercubes［J］.Applied Mathematics and Computation，2019，347：342-353.

［20］BONDY J A.Murty，Graph Theory［M］.New York：Springer，2007.

［21］XU M.The connectivity and super connectivity of bubble-sort graph［J］.Acta Mathematicae Applicatae Sinica-Chinese，2012，35：789-794.

［22］CHENG E，LIPTK L.Linearly many faults in Cayley graphs generated by transposition trees［J］.Information Sciences，2007，177：4877-4882.

［23］LI S.Some Topics on Generalized Connectivity of Graphs［D］.Tianjing：Nankai University，2012.

The generalized 4-connectivity of bubble-sort graphs

Wang Yanling1， Feng Wei2

（1. College of Mathematics and Information Science， Henan Normal University， Xinxiang 453007， China;

2. College of Mathematics and Physics， Inner Mongolia Minzu University， Tongliao 028043， China）

Abstract： Let SV（G） be a vertex set and |S|k for 2kn， 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）∶SV（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（Bn） of the bubble-sort graph Bn and get κ4（Bn）=n-2 when n3.

Keywords： generalized 4-connectivity; internally disjoint; bubble-sort graphs; paths

［責任編校 陳留院 趙曉華］