On (d, 2)-dominating numbers of binary undirected de Bruijn graphs

Changhong Lu, Juming Xu, Kemin Zhang

Abstract

In this paper, we show that: (i) For n-dimensional undirected binary de Bruijn graphs, UB(n), n⩾4, there is a vertex x=x1x̄1x̄1⋯x̄1x1<math><mtext>x=x</mtext><msub><mi></mi><mn>1</mn></msub><mtext>x</mtext><mtext>̄</mtext><msub><mi></mi><mn>1</mn></msub><mtext>x</mtext><mtext>̄</mtext><msub><mi></mi><mn>1</mn></msub><mtext>⋯</mtext><mtext>x</mtext><mtext>̄</mtext><msub><mi></mi><mn>1</mn></msub><mtext>x</mtext><msub><mi></mi><mn>1</mn></msub></math> (x1=1 or 0) such that for any other vertex t there exist at least two internally disjoint paths of length at most n−1 between x and t in UB(n), i.e., the (n−1,2)-dominating number of UB(n) is equal to one. (ii) For n⩾5, let S={100⋯01,011⋯10}. For any other vertex t there exist at least two internally disjoint paths of length at most n−2 between t and S in UB(n), i.e., the (n−2,2)-dominating number of UB(n) is no more than 2.
BibTeX
@article{lu2000d,
  author = {Changhong Lu and Juming Xu and Kemin Zhang},
  title = {{On (d, 2)-dominating numbers of binary undirected de Bruijn graphs}},
  journal = {Discret. Appl. Math.},
  year = {2000},
  doi = {10.1016/s0166-218x(00)00199-2},
}

Loading related content...

Figure