On balance index sets of rooted trees. (English) Zbl 1224.05446

Kwong, Harris

Ars Comb. 91, 373-382 (2009).

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.

MSC:

05C78	Graph labelling (graceful graphs, bandwidth, etc.)
05C05	Trees

Keywords:

friendly labeling; balanced labeling; balance index set