具有给定稳定数和连通性的极值图

如果n阶图G的稳定数为a，连通数为k，则称之为一个（n,a,k)图，chvatal和Edos证明如果a≤k，则G是一个哈密尔顿图，如果a-1≥k≥2，图G多大才能保证存在一个哈密尔顿圈？本文回答了这个问题，进一步特征化极大数目的边的图，即给出了极图（n,a,k)的特征。

Extremal graphs with given stability number and connectivity(I)

Call a graph G an (n,α,k) graph if G is of order n with stability number α and connectivity k.Chvátal and Erd?s show that if α≤k,then G is hamiltonian.Now if α-1≥k≥2,how big should G be to ensure the existence of a hamiltonian circult? In this paper we answer this question and further characterize the extremal (n,α,k)-graphs-the ones with maximum numbers of edges.