On a Conjecture Concerning the Friendly Index Sets of Trees.
Ebrahim Salehi, Shipra De · Ars Combinatoria · 2009
For a graph G = (V,E) and a binary labeling f : V (G) → Z2, let vf (i) = |f−1(i)|. The labling f is said to be friendly if |vf (1)−vf (0)| ≤ 1. Any vertex labeling f : V (G) → Z2 induces an edge labeling f∗ : E(G) → Z2 defined by f∗(xy) = |f(x)− f(y)|. Let ef (i) = |f∗−1(i)|. The friendly index set of the graph G, denoted by FI(G), is defined by FI(G) = {|ef (1)− ef (0)| : f is a friendly vertex labeling of G }. In [15] Lee and Ng conjectured that the friendly index sets of trees will form an arithmetic progression. This conjecture has been mentioned in [17] and other manuscripts. In this paper we will first determine the friendly index sets of certain caterpillars of diameter four. Then we will disprove the conjecture by presenting an infinite number of trees whose friendly index sets do not form an arithmetic progression.