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 UBG(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.
2000 AMS Subject Classification:
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).