Authors: Amos Korman David Peleg Yoav Rodeh
Publish Date: 2008/09/13
Volume: 57, Issue: 4, Pages: 641-652
Abstract
Let f be a function on pairs of vertices An f labeling scheme for a family of graphs ℱ labels the vertices of all graphs in ℱ such that for every graph G∈ℱ and every two vertices uv∈G fuv can be inferred by merely inspecting the labels of u and v The size of a labeling scheme is the maximum number of bits used in a label of any vertex in any graph in ℱ This paper illustrates that the notion of universal matrices can be used to efficiently construct flabeling schemesLet ℱn be a family of connected graphs of size at most n and let mathcalCmathcalFn denote the collection of graphs of size at most n such that each graph in mathcalCmathcalFn is composed of a disjoint union of some graphs in ℱn We first investigate methods for translating flabeling schemes for ℱn to flabeling schemes for mathcalCmathcalFn In particular we show that in many cases given an flabeling scheme of size gn for a graph family ℱn one can construct an flabeling scheme of size gn+log log n+O1 for mathcalCmathcalFn We also show that in several cases the above mentioned extra additive term of log log n+O1 is necessary In addition we show that the family of nnode graphs which are unions of disjoint circles enjoys an adjacency labeling scheme of size log n+O1 This illustrates a nontrivial example showing that the above mentioned extra additive term is sometimes not necessary We then turn to investigate distance labeling schemes on the class of circles of at most n vertices and show an upper bound of 15log n+O1 and a lower bound of 4/3log n−O1 for the size of any such labeling scheme
Keywords: