ON (d; 2)-DOMINATING SETS OF BUTTERFLY GRAPHS

For a nonempty and proper subset S of the vertex set V (G) and x 2 V (G n S), an (x; S)-path is a path in G connecting x to some vertex in S. Recently, H. Li and J. M. Xu have de¯ned a new parameter (d;m)-domination number for m-connected graphs which can more accu- rately characterize the reliability of networks. Let S be a nonempty and proper subset of V (G) and y a vertex in Gn S. For a given positive integer d, y is said to be (d;m)-dominated by S if there are at least m internally vertex-disjoint (y; S)-paths in G each of which of length at most d. S is called a (d;m)-dominating set of G. Here, we study (d; 2)-dominating sets of an important class of parallel networks, Butter°ies and then we try to determine their (d;m)-domination number for d = 3 2n.

(d;m)-dominating; Butter°y graphs; wide diameter; 2-connected.