TY - JOUR
T1 - The bondage numbers of extended de Bruijn and Kautz digraphs
AU - Huang, Jia
AU - Xu, Jun Ming
N1 - Funding Information:
It is well known that the topological structure of an interconnection network can be modeled by a connected graph whose vertices represent sites of the network and whose edges represent physical communication links. A minimum dominating set in the graph corresponds to a smallest set of sites selected in the network for some particular uses, such as placing transmitters. Such a set may not work when some communication links happen fault. The fault is possible in real world (hacking, experimental error, terrorism, etc.), so one needs to consider it. What is the minimum number of faulty links which will make all minimum dominating sets of the original network not work any more? Such a minimum number is called the bondage number, which measures the robustness of a network with respect to link failures, wherever a minimum dominating set is required for some application. Motivated by the above relevance of bondage number, one wants to know how to compute it for a network. However, this computation is generally difficult; no *Author to whom all correspondence should be addressed. The authors would like to thank the anonymous referees for their helpful suggestions and comments. The work was supported by NNSF of China (No. 10271114).
PY - 2006
Y1 - 2006
N2 - 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.
AB - 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.
KW - Bondage number
KW - Domination
KW - Extended Kautz digraph
KW - Extended de Bruijn digraph
KW - Kautz digraph
KW - de Bruijn digraph
UR - http://www.scopus.com/inward/record.url?scp=33745825554&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33745825554&partnerID=8YFLogxK
U2 - 10.1016/j.camwa.2005.10.015
DO - 10.1016/j.camwa.2005.10.015
M3 - Article
C2 - 16928568
AN - SCOPUS:33745825554
SN - 0898-1221
VL - 51
SP - 1137
EP - 1147
JO - Computers and Mathematics with Applications
JF - Computers and Mathematics with Applications
IS - 6-7
ER -