一类临界h连通图的原子数目的下界

LOWER BOUND ON THE NUMBER OF ATOMS IN A CLASS OF CRITICALLY H-CONNECTED GRAPHS

苏健基证明,如果G是临界h连通的非完全图,并且最小度δ(G)=3h/2—1,则G中有4个不同的原子。本文将这一结果改进为G中至少有2{f/h}个不同的原子,其中f是G中最大团的基数。当f≥2h时,这一改进的原子个数的下界是最佳的。

Every critically h-connected noncomplete graph with minimal degree (3h/2-1) contains 4 atoms at least (see [2]) . In this paper we prove that every graph of this class of graphs has 2 {f/h} atoms at least, where f is the size of the maximal clique in G, and the lower bound on the number of atoms is best possible when f≥2h.