On the restricted connectivity and superconnectivity in graphs with given girth

The restricted connectivity \(\kappa'(G)\) of a connected graph \(G\) is defined as the minimum cardinality of a vertex-cut over all vertex-cuts \(X\) such that no vertex \(u\) has all its neighbors in \(X\); the superconnectivity \(\kappa_1(G)\) is defined similarly, this time considering only vertices \(u\) in \(G-X\), hence \(\kappa_1(G)\leq \kappa'(G)\). The minimum edge-degree of \(G\) is \(\xi(G)=\min\{d(u)+d(v)-2:uv\in E(G)\}\), \(d(u)\) standing for the degree of vertex \(u\). In this paper, several sufficient conditions yielding \(\kappa_1(G)\geq \xi(G)\) are given, improving a previous related result by \textit{M. A. Fiol} et al. [Ars Comb. 29B, 17--31 (1990; Zbl 0708.05025)] and guaranteeing \(\kappa_1(G)=\kappa'(G)=\xi(G)\) under some additional constraints.

Recommendations

Cites work

Cited in

(21)

This page was built for publication: On the restricted connectivity and superconnectivity in graphs with given girth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q868327)