On m-restricted edge connectivity of undirected generalized De Bruijn graphs

Abstract

An m-restricted edge cut is an edge cut of a connected graph whose removal results in components of order at least m, the minimum cardinality over all m-restricted edge cuts of a graph is its m-restricted edge connectivity. It is known that telecommunication networks with topology having larger m-restricted edge connectivity are locally more reliable for all m≤3. This work shows that if n≥7, then undirected generalized binary De Bruijn graph UB_G(2, n) is maximally m-restricted edge connected for all m≤3, where a graph G is maximally m-restricted edge connected if its m-restricted edge connectivity is equal to the minimum number of edges from any connected subgraphs S to G−S.

Keywords:

• De Bruijn graph
• restricted edge connectivity
• network reliability

2000 AMS Subject Classification:

• 05C40

Acknowledgements

The authors thank the referees very much for their valuable suggestions, which helped us correct some faults and make this paper more readable. Supported by the National Natural Science Foundation of China (grant no. 11126326) and NSF of Guandong Province (S2012010010815).