摘要
本文证明了极大饱和图D(n,k)的一个极值性质:在与D(n,k)具有相同度序列的所有图中,唯有D(n,k)含有最少的K_3子图,并由此推出,在几乎正则图的范围内,k个完全图之并及完全k部多分图均是圈唯一的。本文还用图谱方法,证明了完全二分图K_(m,n)的圈唯一性。
It is proved that among all the graphs which have the same valency sequence as the maximally saturated graph D(n,k) ,only D(n,k) contains the minimum number of K3 subgraphs. With this property,the circuit uniqueness of D(n,k) and its complement is obtained. The circuit uniqueness of the complete bipartite graph Km,n is also proved by using spectral method.
出处
《应用数学》
CSCD
北大核心
1995年第4期385-388,共4页
Mathematica Applicata
关键词
极大饱和图
几乎正则图
圈多项式
圈唯一
简单图
Maximally saturated graph
Nearly regular graph
Circuit polynomial
Circuit u-niqueness
Spectral characterization
