Binary Labeling of Graphs

Let G = (V, E) be a graph. A mapping f: E(G) → {0, l} ^m is called a mod 2 coding of G, if the induced mapping g: V(G) → {0, l} ^m , defined as \(g(v) = \sum\limits_{u \in V,uv \in E} {f(uv)}\) , assigns different vectors to the vertices of G. Note that all summations are mod 2. Let m(G) be the smallest number m for which a mod 2 coding of G is possible. Trivially, m(G) ≥ ?Log₂ |V|?. Recently, Aigner and Triesch proved that m(G) ≤ ?Log₂ |V|? + 4. In this paper, we determine m(G). More specifically, we prove that if each component of G has at least three vertices, then $$mG = \left\{ {\begin{array}{*{20}c} {k,} & {if \left| V \right| \ne 2^k - 2} \\ {k + 1,} & {else} \\ \end{array} ,} \right.$$ where k = ?Log₂ |V|?.