Optimal Radio Labellings of Block Graphs and Line Graphs of Trees

DOI10.1016/J.TCS.2021.08.029MaRDI QIDQ6376251arXivFDO

Authors D. D. Bantva, Daphne Der-Fen Liu

Publication date 29 August 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.TCS.2021.08.029

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

arXiv classification

cs.DMmath.CO

Abstract: A radio labeling of a graph $G$ is a mapping $f$ : $V(G)ightarrow0,1,2,\mathrm{...}$ such that $|f(u)-f(v)|geqdiam(G)+1-d(u,v)$ holds for every pair of vertices $u$ and $v$, where $diam(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(v)-f(u)|:v,uinV(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. Applying the established bound and conditions, we show that several families of block graphs are 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.

This page was built for publication: Optimal Radio Labellings of Block Graphs and Line Graphs of Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6376251)