Transactions on Combinatorics (Jun 2017)
Full edge-friendly index sets of complete bipartite graphs
Abstract
Let $G=(V,E)$ be a simple graph. An edge labeling $f:Eto {0,1}$ induces a vertex labeling $f^+:VtoZ_2$ defined by $f^+(v)equiv sumlimits_{uvin E} f(uv)pmod{2}$ for each $v in V$, where $Z_2={0,1}$ is the additive group of order 2. For $iin{0,1}$, let $e_f(i)=|f^{-1}(i)|$ and $v_f(i)=|(f^+)^{-1}(i)|$. A labeling $f$ is called edge-friendly if $|e_f(1)-e_f(0)|le 1$. $I_f(G)=v_f(1)-v_f(0)$ is called the edge-friendly index of $G$ under an edge-friendly labeling $f$. The full edge-friendly index set of a graph $G$ is the set of all possible edge-friendly indices of $G$. Full edge-friendly index sets of complete bipartite graphs will be determined.
Keywords
