Binary labeling of graphs (Q1359371)

A mapping \(f: E\to\{0,1\}^m\) of a graph \(G=(V,E)\) is called a mod 2 coding of \(G\), if the induced mapping \(g:V\to \{0,1\}^m\), defined by \(g(v)= \sum_{u\in V,\{u,v\}\in E}f(\{u,v\})\) assigns a different number to each vertex, where summations are taken modulo 2. This paper studies the number \(m(G)\), which is the smallest value of \(m\) for which a mod 2 coding exists. A necessary and sufficient condition for the existence of a mod 2 coding is that every connected component of \(G\) has at least three vertices. This paper establishes a precise formula for \(m(G)\): it is shown that for graphs with no connected component with less than three vertices, \(m(G)=\lceil\log_2|V|\rceil\), if \(|V|\) is not of the form \(2^k-2\), and \(m(G)=\lceil\log_2|V|+1\rceil\), if \(|V|\) is of the form \(2^k-2\), for some integer \(k\).