Coding the vertexes of a graph

Author

Breuer, Melvin A.

Volume

Issue

fYear

1966

fDate

4/1/1966 12:00:00 AM

Firstpage

148

Lastpage

153

Abstract

Given a graph $G$ of $n$ nodes. We wish to assign to each node $i(i = 1, 2, \\cdots n)$ a unique binary code $c_{i}$ of length $m$ such that, if we denote the Hannuing distance between $c_{i}$ and $c_{j}$ as $H(c_{i}, c_{j})$ , then $H(c_{i}, c_{j})\\leq T$ if nodes $i$ and $j$ are adjacent (i.e., connected by a single branch), and $H(c_{i}, c_{j}) \\geq T+1$ otherwise. If such a code exists, then we say that $G$ is doable for the value of $T$ and tn associated with this code. In this paper we prove various properties relevent to these codes. In particular we prove 1) that for every graph $G$ there exists an $m$ and $T$ such that $G$ is doable, 2) for every value of $T$ there exists a graph $\\tilde{G}$ which is not $T$ doable, 3) if $G$ is $T\´$ doable, then it is $T\´+ 2p$ doable for $p = 0, 1, 2, \\cdots$ , and is doable for all $T \\geq 2T\´$ if $T\´$ is odd, and is doable for all $T \\geq 2T\´ + 1$ if $T\´$ is even. In theory, the code can be synthesized by employing integer linear programming where either $T$ and/or $m$ can be minimized; however, this procedure is computationally infeasible for values of $n$ and $m$ in the range of about $10$ or greater.

Keywords

Coding; Graph theory; Automata; Binary codes; Error correction; Hamming distance; Integer linear programming; Kinetic theory; Stability;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.1966.1053860

Filename

1053860

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=907371