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, \dots, 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.