Minimally $k$-equitable Labeling of Butterfly and Benes Networks

Abstract

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.