Non-κ-critical vertices in graphs

Authors
Publisher
North-Holland
Publication Date
Source
Legacy

Abstract

PII: 0012-365X(83)90009-2 Discrete Mathematics 44 (1983) 105-110 North-Holland Publisbing Company 105 1. NON-IC-CRITICAL VERTOS IN GRAPHS H.J. VELDMAN Depurhnent of Applied Mathematics, Twente University of Technology, Ens&e&, The Nether- lands Received 8 September 1981 Revised 15 February 1982 Let G be a graph with K(G) = h. A vertex u of G is called K-critical if K(G-u) = h -1. Generalizing a resuh of Chartrand, Kaugars and Lick and one of Hamidoune, respectively, we prove: (1) If G(G)>\$h - 1, then G contains at least h + 1 +c(h) non-r-critical vertices, where IS(~) = 0 if h is odd and e(h) = 1 if h is even; (2) If G contains at most one vertex of degree not exceeding \$h - 1, then G has at least [email protected](h) noncritical vertices. The results are best possible in the sense that under either condition there exist, for every h, infinitely many graphs containing exactly the specified minimum number of noncritical vertices. All concepts not defined here may be found in Harary [3]. A graph G is h-connected if for every S c V(G) with ISI < h, the graph G -S is connected (G -S is an abbreviation of (V(G) - S), the subgraph of G induced by V(G) - S). The connectivity of G, denoted K(G), is the maximum value of F. for which G is h-connected. A vertex II of G is called K-critical (or just critical) if K(G --a) = K(G) - 1. The number of noncritical vertices of 6 is denoted by T(G). We say that G is criticalZy h-connected if K(G) = h and ~(6) = 0. If A c V(G), then N(A) denotes the set of all vertices of G -A adjacent to vertices in A. Furthermore, d is defined as V(G)-(A UN(A)). A subset T of V(G) is a vertex cut of G if G - T is disconnected. A k-uerzex cut is a vertex cut of k elements. A minimum vertex cut is a K(G)-vertex cut. Following Hamidoune, we define a subset A of V(G) to be a fragment of G if d #\$I and N(A) is a minimum vertex cut of G. If A is a fragment and N(A) = 7’, then A is said to be a fragment with respect to T. An endfrigment is a fragment that

Seen <100 times