不含某类子图的k-连通图中的一个结果  

A result on k-connected graphs without a kind of subgraphs

作　　者：杨迎球 令狐荣涛 Yang Yingqiu;Linghu Rongtao(School of Mathematics and Physics,Anshun University,Anshun 561000,Guizhou,China)

机构地区：[1]安顺学院数理学院,贵州安顺561000

出　　处：《安顺学院学报》2018年第4期130-133,共4页Journal of Anshun University

基　　金：贵州省科技厅;安顺市人民政府;安顺学院联合基金项目(黔科合LH字[2014]7500)

摘　　要：如果将k-连通图G中的一条边收缩之后仍然得到一个k-连通图,则称这条边是G的一条k-可收缩边(简称可收缩边)。一个不含任何可收缩边的非完全k-连通图称为收缩临界k-连通图。2000年,Ando等证明了如下结论:设k≥4是一个整数,G是一个不含K-4的收缩临界k-连通图,则k是一个偶数,并且G中的每一个顶点都至少含在2个三角形中。文章进一步加强Ando等的结论,证明:设k≥3是一个整数,G是一个不含K-4的k-连通图,若G中存在至多含在一个三角形上的顶点,则每一个这样的顶点都关联一条k-可收缩边。An edge of a k- connected graph is said to be k-contractible edge （simply contractible edge） if its contraction again results in a k connected graph. A non - complete k -connected graph without any contractible edges is called a contraction critical k-connected graph. In 2000, Ando et. al. proved the following result： Let k≥4 be an integer, G be a k-free contraction critical k-connected graph. Then k is even and every vertex in G is contained in at least two triangles. In this paper, we further strengthen the result of Ando et al. and prove the following result： Let k ≥3 be an integer, G be a k-free k-connected graph. If G contains some vertices such that every of them is contained in at most one triangle, then every of these vertices is incident with a k-contractible edge.

关 键 词：K-连通图 k-可收缩边 连通分支 

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