Cartesian powers of graphs and consecutive radio labelings

arXiv1212.1977MaRDI QIDQ6237872FDOQ6237872

Authors: Amanda Niedzialomski 

Publication date: 10 December 2012

Abstract: For $kinmathbb{Z}^{+}$ and $G$ a simple connected graph, a $k$-radio labeling $$ of $G$ requires all pairs of distinct vertices $u$ and $v$ to satisfy $|f(u)-f(v)|geqk+1-d(u,v)$. When $k=1$, this requirement gives rise to the familiar labeling known as vertex coloring for which each vertex of a graph is labeled so that adjacent vertices have different "colors". We consider $k$-radio labelings of $G$ when $k=diam(G)$. In this setting, no two vertices can have the same label, so graphs that have radio labelings of consecutive integers are one extreme on the spectrum of possibilities. Examples of such graphs of high diameter are especially rare and desirable. We construct examples of arbitrarily high diameter, and explore further the tool we used to do this -- the Cartesian product of graphs -- and its effect on radio labeling.

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

This page was built for publication: Cartesian powers of graphs and consecutive radio labelings

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