On M-restricted Edge Connectivity Of Undirected Generalized De Bruijn Graphs

Generalized De Bruijn networks make up some deficiencies of De Bruijn networks, they can contain any number of nodes, this work studies their edge connectivity. Edge connectivity of graphs is an important parameter for the measure of telecommunication network reliability, but it does not work when one compares the reliability of maximally edge-connected networks that have the same number of nodes and links. To solve the previous problem, the concept of m-restricted edge connectivity has been introduced. The known results show that telecommu-nication networks with larger m-restricted edge connectivity are locally more reliable, where m≤3.This work studies the m-restricted edge connectivity of generalized De Bruijn graphs, as a result, we obtain the following observations.Theorem2.2.1. Undirected generalized De Bruijn graph UBG(2, n) is maximally restricted edge connected if n≤7.Theorem2.2.2. Undirected generalized De Bruijn graph UBG(2, n) is maximally3-restricted edge connected if n≤7.Theorem3.2.1. Undirected generalized De Bruijn graph UBG(3, n) has restricted edge connectivity6≤λ’≤8if n>25; and6≤λ’≤7if9≤n≤24.Theorem4.2.1. Undirected generalized De Bruijn graph UBG(d, n) is maximally restricted edge connected if n> d(d2-1) and d≥4.These observations can be employed to analyse the reliability of telecommunication net-work with topology being generalized De Bruijn graphs, and improve the accuracy of the com-putation.