Optimal radio labelings of block graphs and line graph of trees

2021 Research Paper

A radio labeling of a graph G is a mapping f : V(G) → {0, 1, 2,...} such that |f(u)-f(v)| >=d(G)+1-d(u,v) holds for every pair of vertices u and v, where d(G) is the diameter of G and d(u,v) is the distance between u and v in G. The radio number of G, denoted by rn(G), is the smallest t such that G admits a radio labeling with t=max{|f(u)-f(v)| : u, v in V(G)}. A block graph is a graph such that each block (induced maximal 2-connected subgraph) is a complete graph. In this paper, a lower bound for the radio number of block graphs is established. The block graph which achieves this bound is called a lower bound block graph. We prove three necessary and sufficient conditions for lower bound block graphs. Moreover, we give three sufficient conditions for a graph to be a lower bound block graph. Using these results, we present several families of lower bound block graphs, including the level-wise regular block graphs and the extended star of blocks. The line graph of a graph G(V,E) has E(G) as the vertex set, where two vertices are adjacent if they are incident edges in G. We extend our results to trees as trees and its line graphs are block graphs. We prove that if a tree is a lower bound block graph then, under certain conditions, its line graph is also a lower bound block graph, and vice versa. Consequently, we show that the line graphs of many known lower bound trees, excluding paths, are lower bound block graphs.

Authors: Dr. Devsi Bantva, Devsi Bantva, Samir Vaidya and Sanming Zhou
Journal: Theoretical Computer Science (Elsevier)