关于拟k-连通图的一个注释  

A note on quasi k-connected graphs

作　　者：林晓霞[1] LIN Xiaoxia(Teachers College,Jimei University,Xiamen 361021,Fujian,China)

机构地区：[1]集美大学师范学院,福建厦门361021

出　　处：《运筹学学报》2021年第1期137-140,共4页Operations Research Transactions

基　　金：国家自然科学基金(No.11871246);福建省自然科学基金(No.2016J01666)。

摘　　要：G是一个k-连通图,T是G的一个k-点割,若G-T可被划分成两个子图G_(1),G_(2),且|G_(1)|≥2,|G_(2)|≥2,则称T是G的一个非平凡点割。假定G是一个不含非平凡(k-1)点割的(k-1)-连通图,则称G是一个拟k-连通图。证明了对任意一个k≥5且t>k/2的整数,若G是一个不含(K_(2)+tK_(1))的k-连通图,且G中任意两个不同点对v,w,有d(v)+d(w)≥3k/2+t,则对G中的任意一个点,存在一条与之关联的边收缩后可以得到一个拟k-连通图,且G中至少有|V(G)|/2条边使得收缩其中任意一条边后仍是拟k-连通的。Let G be a k-connected graph,and T be a k-vertex-cut of a k-connected graph G.If G-T can be partitioned into subgraphs G_(1) and G_(2) such that|G_(1)|≥2,|G_(2)|≥2,then we call T a nontrivial k-vertex-cut of G.Suppose that G is a(k-1)-connected graph without nontrivial(k-1)-vertex-cut,then we call G a quasi k-connected graph.In this paper,we prove that for any integer k≥5 and t>k/2,if G is a(K_(2)+tK_(1))-free k-connected graph for which d(v)+d(w)≥3 k/2+t for any pair v,w of distinct vertices of G,then every vertex of G is incident with an edge whose contraction yields a quasi k-connected graph,and so there are at least|V(G)|/2 edges of G such that the contraction of every member of the results in a quasi k-connected graph.

关 键 词：拟k-连通图 连通分支 

分 类 号：O157.5[理学—基础数学]