The Vertices of Lower Degree in Contraction-Critical kappa Connected Graphs

摘要

Let G be a contraction-critical kappa connected graph. It is known (see Graphs and Combinatorics, 7 (1991) 15-21) that the minimum degree of G is at most left perpendicular5 kappa/4right perpendicular - 1. In this paper we show that if G has at most one vertex of degree kappa, then either G has a pair of adjacent vertices such that each of them has degree at mostleft perpendicular5 kappa/4right perpendicular - 1, or there is a vertex of degree 11: whose neighborhood has a vertex of degree at most left perpendicular4 kappa/3right perpendicular - 1. Moreover, if the minimum degree of G equals to 5 kappa/4 - 1(and thus kappa = 0 mod 4), Su showed that G has kappa vertices of degree 5 kappa/4 - 1, guessed that G has 3 kappa/2 such vertices (see Combinatorics Graph Theory Algorithms and Application (Yousef Alavi et. al Eds.), World Scientific, 1993, 329-337). Here we verify that this is true.