A New property Of binary undirected de bruijn graphs

Xu Junming; Lu Changhong; Zhang Kemin

doi:10.1007/BF02731956

A New property Of binary undirected de bruijn graphs

Xu Junming^*
, Lu Changhong
, Zhang Kemin

^*Corresponding author for this work

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

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.1007/BF02731956
State	Published - Jan 2000
Externally published	Yes

Keywords

1991 MR Subject Classification: 05C40, 68M10, 68R10
Dominating number
Length of path
O157.5
O157.9
Wide-diameter
de Bruijn graph

Access to Document

10.1007/BF02731956

Cite this

@article{5f59307c2d134c2f81295cca1629a633,

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 = "1991 MR Subject Classification: 05C40, 68M10, 68R10, Dominating number, Length of path, O157.5, O157.9, Wide-diameter, de Bruijn graph",

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

year = "2000",

month = jan,

doi = "10.1007/BF02731956",

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 - Junming, Xu

AU - Changhong, Lu

AU - Kemin, Zhang

PY - 2000/1

Y1 - 2000/1

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 - 1991 MR Subject Classification: 05C40, 68M10, 68R10

KW - Dominating number

KW - Length of path

KW - O157.5

KW - O157.9

KW - Wide-diameter

KW - de Bruijn graph

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

U2 - 10.1007/BF02731956

DO - 10.1007/BF02731956

M3 - 文章

AN - SCOPUS:51649160143

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