zbMATH — the first resource for mathematics

On balance index sets of rooted trees. (English) Zbl 1224.05446
Summary: Any vertex labeling \(f\:V\to \{0,1\}\) of the graph \(G=(V,E)\) induces a partial edge labeling \(f^{*}:E\to \{0,1\}\) defined by \(f^{*}(uv)=f(u)\) if and only if \(f(u)=f(v)\). The balance index set of \(G\) is defined as \(\{| f^{*-1}(0)-f^{*-1}(1)| \: | f^{-1}(0)-f^{-1}(1)| \leq 1\}\). In this paper, we first determine the balance index sets of rooted trees of height not exceeding two, thereby completely settling the problem for trees with diameter at most four. Next, we show how to extend the technique to rooted trees of any height, which allows us to derive a method for determining the balance index set of any tree.
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C05 Trees