具有给定稳定数和连通性的极值图(英文)

Extremal graphs with given stability number and connectivity(Ⅰ)

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

Call a graph G an (n,α,k) graph if Gis of order n with stabili ty number α and connectivity k. Chvátal and Erds 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 o nes with maximum numbers of edges.