On a Conjecture Concerning the Friendly Index Sets of Trees

Abstract

For a graph $G=(V,E)$ and a binary labeling $f:V(G)\to {\mathbb{Z}}_2$, let $v_f(i)=|f^{-1}(1)|$. The labeling $f$ is said to be friendly if $|v_f(1)–v_f(0)|\le 1$. Any vertex labeling $f:V(G)\to {\mathbb{Z}}_2$ induces an edge labeling $f^{\ast }:E(G)\to {\mathbb{Z}}_2$ defined by $f^{\ast }(xy)=|f(x)–f(y)|$. Let $e_f(i)=|f^{\ast -1}(i)|$. The friendly index set of the graph $G$, denoted by $FI(G)$, is defined by

$$FI(G)=\{|e_f(1)–e_f(0)|:f\text{ 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.