On hamiltonian colorings for some graphs |
| |
Authors: | Yufa Shen Wenjie He Donghong He |
| |
Affiliation: | a Department of Mathematics and Physics, Hebei Normal University of Science and Technology, Qinhuangdao 066004, PR China b Applied Mathematics Institute, Hebei University of Technology, Tianjin 300130, PR China c Center for Mathematics of Hebei Province, Hebei Normal University, Shijiazhuang 050016, PR China |
| |
Abstract: | For a connected graph G and any two vertices u and v in G, let D(u,v) denote the length of a longest u-v path in G. A hamiltonian coloring of a connected graph G of order n is an assignment c of colors (positive integers) to the vertices of G such that |c(u)−c(v)|+D(u,v)≥n−1 for every two distinct vertices u and v in G. The value of a hamiltonian coloring c is the maximum color assigned to a vertex of G. The hamiltonian chromatic number of G is taken over all hamiltonian colorings c of G. In this paper we discuss the hamiltonian chromatic number of graphs G with . As examples, we determine the hamiltonian chromatic number for a class of caterpillars, and double stars. |
| |
Keywords: | Hamiltonian colorings Hamiltonian chromatic number Caterpillars Double stars |
本文献已被 ScienceDirect 等数据库收录! |
|