Total Difference Labeling of Regular Infinite Graphs

Abstract

Given a graph $G$, a \textit{$k$-total difference labeling} of the graph is a total labeling $f$ from the set of edges and vertices to the set $\{1,2,\cdots k\}$ satisfying that for any edge $\{u,v\}$, $f(\{u,v\})=|f(u)-f(v)|$. If $G$ is a graph, then ${\chi }_{td}(G)$ is the minimum $k$ such that there is a $k$-total difference labeling of $G$ in which no two adjacent labels are identical. We extend prior work on total difference labeling by improving the upper bound on ${\chi }_{td}(K_n)$ and also by proving results concerning infinite regular graphs.

20 pages, submitted to Involve. This version contains some results, in particular, the sections on the sequences OS, E, D, M_i1 and M_i2, the questions about random graphs, and the part on saturated and supersaturated graphs, which are not in the version sent to Involve

References in corpus (1)

• Total Difference Chromatic Numbers of Graphs