Friendly Indices and Fully Cordial Graphs

Abstract

For a graph $G=(V,E)$ with a coloring $f:V(G)\to {\mathbb{Z}}_2$, let $v_f(i)=|f^{-1}(i)|$. We say $f$ is friendly if $|v_f(1)–v_f(0)|\le 1$. The coloring $f$ induces an edge labeling $f_{+}:E\to {\mathbb{Z}}_2$ defined by $f_{+}(uv)=f(u)+f(v)\mathrm{mod}2$, for each $uv\in E$. Let $e_f=|f_{+}^{-1}(i)|$. The friendly index set of the graph $G$, denoted by $FI(G)$, is defined by $\{|e_f(1)–e_f(0)|:f\text{ is a friendly coloring of }G\}$. We say $G$ is fully cordial if $FI(G)=\{|E|,|E|–2,|E|–4,\dots ,|E|–2[(\genfrac{}{}{0ex}{}{|E|}{2})]\}$. In this paper, we develop a new technique to calculate friendly index sets without labeling vertices, and we develop a technique to create fully cordial graphs from smaller fully cordial graphs. In particular, we show the first examples of fully cordial graphs that are not trees, as well as new infinite classes of fully cordial graphs.