The bondage numbers of extended de Bruijn and Kautz digraphs

Jia Huang, Jun Ming Xu

Research output: Contribution to journalArticle

13 Scopus citations

Abstract

In this paper, we consider the bondage number b(G) for a digraph G, which is defined as the minimum number of edges whose removal results in a new digraph with larger domination number. This parameter measures to some extent the robustness of an interconnection network with respect to link failures. By constructing a family of minimum dominating sets, we compute the bondage numbers of the extended de Bruijn digraph and the extended Kautz digraph. As special cases, we obtain for the de Bruijn digraph B(d, n) and the Kautz digraph K(d, n) that b(B(d, n)) = d if n is odd and d ≤ b(B(d, n)) < 2d if n is even, and b(K(d, n)) = d + 1.

Original languageEnglish (US)
Pages (from-to)1137-1147
Number of pages11
JournalComputers and Mathematics with Applications
Volume51
Issue number6-7
DOIs
StatePublished - 2006

Keywords

  • Bondage number
  • Domination
  • Extended Kautz digraph
  • Extended de Bruijn digraph
  • Kautz digraph
  • de Bruijn digraph

ASJC Scopus subject areas

  • Modeling and Simulation
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'The bondage numbers of extended de Bruijn and Kautz digraphs'. Together they form a unique fingerprint.

  • Cite this