A new property of binary undirected de Bruijn graphs (Q1976593): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(3 intermediate revisions by 2 users not shown) | |||
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 | |||
Property / author | |||
Property / author: Jun-Ming Xu / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Chang-hong Lu / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Ke Min Zhang / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: L'udovít Niepel / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 06:26, 5 March 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