Hamiltonian colorings of graphs with long cycles

Abstract: By a hamiltonian coloring of a connected graph $G$ of order $n \geq1$ we mean a mapping $c$ of $V(G)$ into the set of all positive integers such that $\vert c(x) - c(y)\vert\geq n - 1 - D_G(x, y)$ (where $D_G(x, y)$ denotes the length of a longest $x-y$ path in $G$) for all distinct $x, y \in G$. In this paper we study hamiltonian colorings of non-hamiltonian connected graphs with long cycles, mainly of connected graphs of order $n \geq5$ with circumference $n - 2$.

Keywords: connected graphs, hamiltonian colorings, circumference

Classification (MSC2000): 05C15, 05C38, 05C45, 05C78

Full text of the article:

• Compressed PostScript file (180 kilobytes)
• PDF file (132 kilobytes)