Vol. 13, No. 3, 2020

 Recent Issues
 The Journal About the Journal Editorial Board Editors’ Interests Subscriptions Submission Guidelines Submission Form Policies for Authors Ethics Statement ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print) Author Index Coming Soon Other MSP Journals
Total difference chromatic numbers of graphs

Ranjan Rohatgi and Yufei Zhang

Vol. 13 (2020), No. 3, 511–528
Abstract

Inspired by graceful labelings and total labelings of graphs, we introduce the idea of total difference labelings. A $k$-total labeling of a graph $G$ is an assignment of $k$ distinct labels to the edges and vertices of a graph so that adjacent vertices, incident edges, and an edge and its incident vertices receive different labels. A $k$-total difference labeling of a graph $G$ is a function $f$ from the set of edges and vertices of $G$ to the set $\left\{1,2,\dots ,k\right\}$ that is a $k$-total labeling of $G$ and for which $f\left(\left\{u,v\right\}\right)=|f\left(u\right)-f\left(v\right)|$ for any two adjacent vertices $u$ and $v$ of $G$ with incident edge $\left\{u,v\right\}$. The least positive integer $k$ for which $G$ has a $k$-total difference labeling is its total difference chromatic number, ${\chi }_{td}\left(G\right)$. We determine the total difference chromatic number of paths, cycles, stars, wheels, gears and helms. We also provide bounds for total difference chromatic numbers of caterpillars, lobsters, and general trees.

Keywords
graph labelings, graceful graphs, total colorings
Mathematical Subject Classification 2010
Primary: 05C15, 05C78