A new property of binary undirected de Bruijn graphs
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\).
- On \((d,2)\)-dominating numbers of binary undirected de Bruijn graphs
- On the connectivity of the De Bruijn graph
- On the diameter of the generalized undirected de Bruijn graphs.
- A new look at the de Bruijn graph
- A new digraphs composition with applications to de Bruijn and generalized de Bruijn digraphs
- A New Proof and a Generalization of a Theorem of De Bruijn
- scientific article; zbMATH DE number 2050882
- scientific article; zbMATH DE number 5551599
- New bounds on the decycling number of generalized de Bruijn digraphs
- On \((d,2)\)-dominating numbers of binary undirected de Bruijn graphs
- The diameter and Hamiltonian cycle of the generalized de Bruijn graphs \(UG_{\text{B}}(n,n(n+1))\)
- On the diameter of the generalized undirected de Bruijn graphs.
- The undirected de Bruijn graph: fault tolerance and routing algorithms
- Mean eccentricities of de Bruijn networks
- Routing and transmitting problems in de Bruijn networks
- scientific article; zbMATH DE number 2075779 (Why is no real title available?)
- scientific article; zbMATH DE number 2177306 (Why is no real title available?)
- 2-diameter of de Bruijn graphs
- Graphs with the unique path property: Structure, cycles, factors, and constructions
This page was built for publication: A new property of binary undirected de Bruijn graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1976593)
