×

Non-\(\kappa\)-critical vertices in graphs. (English) Zbl 0542.05043

Summary: Let G be a graph with \(\kappa(G)=h\). A vertex \(\nu\) of G is called \(\kappa\)-critical if \(\kappa(G-\nu)=h-1.\) Generalizing a result of G. Chartrand, A. Kaugars and D. R. Lick [Proc. Am. Math. Soc. 32, 63-68 (1972; Zbl 0211.270)] and one of Y. O. Hamidoune [Discrete Math. 32, 257-262 (1980; Zbl 0452.05043)], respectively, we prove: (1) If \(\delta(G)>(3/2)h-1\), then G contains at least \(h+1+\epsilon(h)\) non- \(\kappa\)-critical vertices, where \(\epsilon(h)=0\) if h is odd and \(\epsilon(h)=1\) if h is even; (2) If G contains at most one vertex of degree not exceeding \((3/2)h-1,\) then G has at least \(2+\epsilon(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.

MSC:

05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chartrand, G.; Kaugars, A.; Lick, D. R., Critically \(n\)-connected graphs, Proc. Amer. Math. Soc., 32, 63-68 (1972) · Zbl 0211.27002
[2] Hamidoune, Y. O., On critically \(h\)-connected simple graphs, Discrete Math., 32, 257-262 (1980) · Zbl 0452.05043
[3] Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0797.05064
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.