Codings of graphs with binary edge labels (Q1323484)

Let \(G\) \((V,E)\) be a graph. A mapping \(f:E \to \{0,1\}^ m\) is called a coding of \(G\) if the induced mapping \(g:V \to \{0,1\}^ m\), \(g(v)=\sum_{v \in e}f(e)\), assigns different vectors to the vertices. For the Boolean sum, \(f\) is called a \(B\)-code, and for the mod 2 sum an \(M\)-code. Let \(m_ B(G)\) \((m_ M(G))\) be the smallest length \(m\) for which \(B\)-codes \((M\)-codes) are possible. It is obvious that \(m_ B(G),m_ M(G) \geq \lceil \log_ 2 | V | \rceil\). The authors show (improving the results of \textit{Z. Tuza} [Encoding the vertices of a graph with binary edge labels, Sequences, combinatorics, compression, security, and transmission, Pap. Adv. Int. Workshop, Naples/Italy 1988, 287-299 (1990; Zbl 0696.05058)]) that \(m_ B(G) \leq \lceil \log_ 2 | V | \rceil+1\), \(m_ M (G) \leq \lceil \log_ 2 | V | \rceil+4\). In fact, as the authors say, it seems very likely that \(m_ M (G)\leq \lceil \log_ 2 | V | \rceil+1\).