A new property of binary undirected de Bruijn graphs (Q1976593): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Jun-Ming Xu / rank | |||
Property / author | |||
Property / author: Chang-hong Lu / rank | |||
Property / author | |||
Property / author: Ke Min Zhang / rank | |||
Property / reviewed by | |||
Property / reviewed by: L'udovít Niepel / rank | |||
Revision as of 02:48, 13 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A new property of binary undirected de Bruijn graphs |
scientific article |
Statements
A new property of binary undirected de Bruijn graphs (English)
0 references
29 January 2001
0 references
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\).
0 references
de Bruijn graph
0 references
distance
0 references
disjoint paths
0 references