On maximal 3-restricted edge connectivity of regular graphs

Abstract

Let G be a k-regular graph of order at least nine. It is proved in this work that graph G is maximally 3-restricted edge-connected if it is triangle-free and k>|G|/4+1, the lower bound on k is sharp to some extent. With this observation, we present an expression of the number of edge cuts in the previous graph, which may be employed to analyse the reliability of telecommunication networks.

Keywords:

• regular graph
• edge connectivity
• edge cuts counting
• reliability

2000 AMS Subject Classifications :

• 05C40
• 05C90

Acknowledgements

The author is very grateful to the anonymous referees for their valuable suggestions, which helped me to correct some faults and make this paper more readable. Supported by National Natural Science Foundation of China (Grant No. 10801091); NSF of Guandong province (Grant No. 8152902001000004; 9151051501000072).