ISSN:
1435-5914
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract LetG(V,E) be a graph. A mappingf:E→{0,1} m is called a (binary) coding ofG, if the induced mapping $$g:V \to \{ 0,1\} ^m ,g(\upsilon ) = \sum\limits_{e \mathrel\backepsilon v} {f(e)} $$ , assigns different vectors to the vertices. For the Boolean sum,f is called aB-code, and for the mod 2 sum anM-code. Letm B (G) resp.m M (G) be the smallest lengthm for whichB-codes resp.M-codes are possible. Trivially,m B (G),m M (G) ≥ ⌈log2|V|⌉. Improving results of Z. Tuza we showm B (G)≤⌈log2|V|⌉ + 1,m M (G)≤⌈log2|V|⌉+4.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01202464
Permalink