DocumentCode :
920272
Title :
Addresses for graphs
Author :
Blake, Ian F. ; Gilchrist, James H.
Volume :
19
Issue :
5
fYear :
1973
fDate :
9/1/1973 12:00:00 AM
Firstpage :
683
Lastpage :
688
Abstract :
The problem of labeling the vertices of an undirected, connected graph with binary n -tuple addresses is considered. These addresses are to have the property that if two vertices are a distance k apart in the graph then the Hamming distance between the corresponding addresses must be kd where d is a positive integer which is constant for the graph. Not all graphs may be so addressed. A weak characterization of addressable graphs in terms of the eigenvalues of a certain matrix associated with the graph is given. It is shown that any addressable bipartite graph may always be addressed with d = 1 . For nonbipartite addressable graphs, d must be even, and it is shown that there exist graphs requiring an arbitrarily large d for addressing. An addressing algorithm is given which is guaranteed to address any addressable graph.
Keywords :
Graph theory; Message switching; Application software; Bipartite graph; Computer networks; Costs; Councils; Eigenvalues and eigenfunctions; Hamming distance; Information analysis; Labeling; Routing;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.1973.1055087
Filename :
1055087
Link To Document :
بازگشت