Codings of graphs with binary edge labels
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\).
- Binary labeling of graphs
- Graph labelings in elementary abelian groups
- Codes and \(L(2,1)\)-labelings in Sierpiński graphs
- scientific article; zbMATH DE number 1803166 (Why is no real title available?)
- scientific article; zbMATH DE number 4139806 (Why is no real title available?)
- scientific article; zbMATH DE number 5300021 (Why is no real title available?)
- scientific article; zbMATH DE number 3904625 (Why is no real title available?)
- Set-Valued Graphs: A Survey
- Minimal Graphs with a Specified Code Map Image
- scientific article; zbMATH DE number 969177 (Why is no real title available?)
- Realization of digraphs in Abelian groups and its consequences
- Zero-sum partitions of abelian groups and their applications to magic- and antimagic-type labelings
- Irregular graph labelings in abelian groups
This page was built for publication: Codings of graphs with binary edge labels
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1323484)
