A new property of binary undirected de Bruijn graphs (Q1976593): Difference between revisions

De Bruijn graphs have many good properties and serve as models for interconnection networks. In the note a new property of binary undirected de Bruijn graphs is given. De Bruijn digraphs are defined as iterated line digraphs obtained from a complete directed graph. Another definition of de Bruijn graphs is based on binary sequences of given length. In the case of undirected binary de Bruijn graphs vertices correspond to binary sequences of length \(n\) and two vertices are adjacent if the corresponding sequences differ only in the first or in the last element. It is well known that the diameter of the \(n\)-dimensional undirected de Bruijn graph \(\text{UB}(n)\) is equal to \(n\) and between any two vertices \(x\) and \(y\) there are at least two internally disjoint paths of length less than or equal to \(n\). It is proved that in \(\text{UB}(n)\) exists at least one vertex \(x\) such that for any other vertex \(y\) there are at least two internally disjoint paths of length \(n-1\) from \(x\) to \(y\). In other words there is a vertex of eccentricity at most \(n-1\) and after deleting any vertex from \( \text{UB}(n)\) its eccentricity still remains at most \(n-1\).