On \(k\)-Equitable and \(k\)-Balanced Labelings of Graphs

Abstract

In this paper, we consider labelings of graphs in which the label on an edge is the absolute value of the difference of its vertex labels. Such a labeling using \(\{0,1,2,\ldots,k-1\}\) is called \(k\)-equitable if the number of vertices (resp. edges) labeled \(i\) and the number of vertices (resp. edges) labeled \(j\) differ by at most one and is called \(k\)-balanced if the number of vertices labeled \(i\) and the number of edges labeled \(j\) differ by at most one. We determine which graphs in certain families are \(k\)-equitable or \(k\)-balanced and we give also some necessary conditions on these two labelings.