6533b830fe1ef96bd1296e7c

RESEARCH PRODUCT

Multilevel Bandwidth and Radio Labelings of Graphs

subject

description

This paper introduces a generalization of the graph bandwidth parameter: for a graph G and an integer k ≤ diam(G), the k-level bandwidth Bk(G)of G is defined by Bk(G) = minγ max{|γ(x)-γ(y)|-d(x, y)+1 : x, y ∈ V (G), d(x, y) ≤ k}, the minimum being taken among all proper numberings γ of the vertices of G. We present general bounds on Bk(G) along with more specific results for k = 2 and the exact value for k = diam(G). We also exhibit relations between the k-level bandwidth and radio k-labelings of graphs from which we derive a upper bound for the radio number of an arbitrary graph.