On Friendly Index Sets of $(p,p+1)$-Graphs

Abstract

Let $G$ be a simple graph. Any vertex labeling $f:V(G)\to {\mathbb{Z}}_2$ induces an edge labeling $f^{\ast }:E(G)\to {\mathbb{Z}}_2$ according to $f^{\ast }(xy)=f(x)+f(y)$. For each $i\in {\mathbb{Z}}_2$, define $v_f(i)=|\{v\in V(G):f(v)=i\}|$, and $e_f(i)=|\{e\in E(G):f^{\ast }(e)=i\}|$. The friendly index set of the graph $G$ is defined as $\{|e_f(0)–e_f(1)|:|v_f(0)–v_f(1)|\le 1\}$. We determine the friendly index sets of connected $(p,p+1)$-graphs with minimum degree $2$. Many of them form arithmetic progressions. Those that are not miss only the second terms of the progressions.