Sufficient conditions for optimally and super m-restricted edge-connected graphs with given girth

ABSTRACT

A ${\lambda }_m$-connected graph G is optimally m-restricted edge-connected if its m-restricted edge-connectivity ${\lambda }_m\left(G\right)$ equals the minimum m-edge-degree ${\xi }_m\left(G\right)$, and super m-restricted edge-connected if all minimum m-restricted edge cuts are trivial. In this study, a bound for the size of graphs with girth greater than any given integer l $(l\ge 3)$ is obtained firstly. Then the second minimum degree conditions for optimally and super m-restricted edge-connected graphs with girth greater than l are provided. Furthermore, the relationship between optimally m-restricted edge connectivity and optimally $(m+1)$-restricted edge connectivity is characterized.

Keywords:

• Girth
• m-restricted edge connectivity
• ${\lambda }_m$-optimal
• super-${\lambda }_m$

AMS 2000 subject classifications:

• 05C70
• 05C90

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work is supported by National Natural Science Foundation of China (NNSF of China) [11126726, 11971106], NSF of Guangdong Province [2014A030310413, 2020A1515010555].