华中师范大学学报（自然科学版）
華中師範大學學報（自然科學版）
화중사범대학학보（자연과학판）
JOURNAL OF CENTRAL CHINA NORMAL UNIVERSITY(NATURAL SCIENCES)
2000年
4期
382-386
,共5页
极(n,α,k)-图%稳定数%Hamiltonian图%连通性
極(n,α,k)-圖%穩定數%Hamiltonian圖%連通性
겁(n,α,k)-도%은정수%Hamiltonian도%련통성
extremal (n,α,k)-graph%stability number%hamiltonian graph%connectivity
如果n阶图G的稳定数为α,连通数为k,则称之为一个(n,α,k)-图.Chvátal和Erd?s证明如果α≤k,则G是一个哈密尔顿图.如果α-1≥k≥2,图G多大才能保证存在一个哈密尔顿圈? 本文回答了这个问题,进一步特征化极大数目的边的图,即给出了极图(n,α,k)的特征.
如果n階圖G的穩定數為α,連通數為k,則稱之為一箇(n,α,k)-圖.Chvátal和Erd?s證明如果α≤k,則G是一箇哈密爾頓圖.如果α-1≥k≥2,圖G多大纔能保證存在一箇哈密爾頓圈? 本文迴答瞭這箇問題,進一步特徵化極大數目的邊的圖,即給齣瞭極圖(n,α,k)的特徵.
여과n계도G적은정수위α,련통수위k,칙칭지위일개(n,α,k)-도.Chvátal화Erd?s증명여과α≤k,칙G시일개합밀이돈도.여과α-1≥k≥2,도G다대재능보증존재일개합밀이돈권? 본문회답료저개문제,진일보특정화겁대수목적변적도,즉급출료겁도(n,α,k)적특정.
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.
