糙度和k-覆盖图  

TOUGHNESS AND k-COVERED GRAPHS

作　　者：刘桂真[1] 

机构地区：[1]山东大学,济南250100

出　　处：《应用数学学报》1992年第3期397-402,共6页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金

摘　　要：一、引言 我们所考虑的图是指没有环和重边的有限无向图。在本文中未加说明的定义和记号请参见文献[2]。设G是一个具有顶点集V(G)和边集E(G)的图。对V(G)的一个子集S,用G[S]表示G的由S导出的子图且令G—S=G[V(G)\S]。若G[S]不含边,则称S为独立集。我们用d_G(x)表示G中顶点x的次数,用Γ_G(x)表示G中与顶点x邻接的顶点集合。对令.我们分别用△(G)和ω(G)表示G的顶点的最大次数和连通分支数。若对任意的且ω(G—S)>A graph G is k-covered if each edge of G belongs to a k-factor.A connected graph G is said to be t-tough if t (G-S)≤|S| for anysubset S of V(G) with (G-S)>1,where (G-S) is the number of components of G-s.In this paper it is proved that every k-tough graph is k-covered if k|V(G)| is even,|V(G)|≥k+1 and k>1.Thereby a result by H.Enomoto et al.is generalized.

关 键 词：糙度 K-覆盖图 图论 

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