A new property of binary undirected de Bruijn graphs

Junming Xu; Changhong Lu; Kemin Zhang

doi:10.1142/S0252959900000066

A new property of binary undirected de Bruijn graphs

Junming Xu^*
, Changhong Lu
, Kemin Zhang

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

The authors obtain a new property of the n-dimensional binary undirected de Bruijn graph UB(n) for n ≥ 4, namely, there is a vertex x such that for any other vertex y there exist at least two internally disjoint paths of length at most n - 1 between x and y in UB(n). The result means that the (n - 1, 2)-dominating number of UB(n) is equal to one if n ≥ 4.

Original language	English
Pages (from-to)	39-42
Number of pages	4
Journal	Chinese Annals of Mathematics. Series B
Volume	21
Issue number	1
DOIs	https://doi.org/10.1142/S0252959900000066
State	Published - 2000
Externally published	Yes

Keywords

De bruijn graph
Dominating number
Length of path
Wide-diameter

Access to Document

10.1142/S0252959900000066

Cite this

@article{7eb0223095a14eaba2f9033673b7a0f5,

title = "A new property of binary undirected de Bruijn graphs",

abstract = "The authors obtain a new property of the n-dimensional binary undirected de Bruijn graph UB(n) for n ≥ 4, namely, there is a vertex x such that for any other vertex y there exist at least two internally disjoint paths of length at most n - 1 between x and y in UB(n). The result means that the (n - 1, 2)-dominating number of UB(n) is equal to one if n ≥ 4.",

keywords = "De bruijn graph, Dominating number, Length of path, Wide-diameter",

author = "Junming Xu and Changhong Lu and Kemin Zhang",

year = "2000",

doi = "10.1142/S0252959900000066",

language = "英语",

volume = "21",

pages = "39--42",

journal = "Chinese Annals of Mathematics. Series B",

issn = "0252-9599",

publisher = "Springer Verlag",

number = "1",

}

TY - JOUR

T1 - A new property of binary undirected de Bruijn graphs

AU - Xu, Junming

AU - Lu, Changhong

AU - Zhang, Kemin

PY - 2000

Y1 - 2000

N2 - The authors obtain a new property of the n-dimensional binary undirected de Bruijn graph UB(n) for n ≥ 4, namely, there is a vertex x such that for any other vertex y there exist at least two internally disjoint paths of length at most n - 1 between x and y in UB(n). The result means that the (n - 1, 2)-dominating number of UB(n) is equal to one if n ≥ 4.

AB - The authors obtain a new property of the n-dimensional binary undirected de Bruijn graph UB(n) for n ≥ 4, namely, there is a vertex x such that for any other vertex y there exist at least two internally disjoint paths of length at most n - 1 between x and y in UB(n). The result means that the (n - 1, 2)-dominating number of UB(n) is equal to one if n ≥ 4.

KW - De bruijn graph

KW - Dominating number

KW - Length of path

KW - Wide-diameter

UR - https://www.scopus.com/pages/publications/85037519766

U2 - 10.1142/S0252959900000066

DO - 10.1142/S0252959900000066

M3 - 文章

AN - SCOPUS:85037519766

SN - 0252-9599

VL - 21

SP - 39

EP - 42

JO - Chinese Annals of Mathematics. Series B

JF - Chinese Annals of Mathematics. Series B

IS - 1

ER -

A new property of binary undirected de Bruijn graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this