Codings of graphs with binary edge labels
Tóm tắt
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.
Tài liệu tham khảo
Aigner, M., Triesch, E.: Irregular assignments of trees and forests. SIAM J. Discret Math.3, 439–449 (1990)
Aigner, M., Triesch, E.: Irregular assignments and two problems à la Ringel. In: Topics in combinatorics and graph theory (R. Bodendieck, R. Henn, eds.). Physics Verlag 1990, 29–36
Golomb, S. W.: How to number a graph. In: Graph theory and computing (R.C. Read, ed.). Academic Press 1972, 23–37
Hedge, S.M.: Set-sequential graphs. to be published
Lehel, J.: Facts and quests on degree irregular assignments. to be published
Ringel, G.: Problem No. 25. In: Theory of graphs and its applications. Proc. Symp. Smolenice 1963 (M. Fiedler, ed.). Publ. House Czech. Acad. Sciences 1964
Tuza, Z.: Encoding the vertices of a graph with binary edge-labels. In: Sequences-combinatorics, compression, security and transmission (R.M. Capocelli, ed.). Springer-Verlag 1990, 287–299