Minimally \(k\)-equitable Labeling of Butterfly and Benes Networks

A labeling of the vertices of a graph with distinct natural numbers induces a natural labeling of its edges: the label of an edge \( (x, y) \) is the absolute value of the difference of the labels of \( x \) and \( y \). We say that a labeling of the vertices of a graph of order \( n \) is minimally \( k \)-equitable if the vertices are labeled with \( 1, 2, \ldots, n \) and in the induced labeling of its edges, every label either occurs exactly \( k \) times or does not occur at all. In this paper, we prove that Butterfly and Benes networks are minimally \( 2^r \)-equitable, where \( r \) is the dimension of the networks.