Recent Advancements in Graph Theory

28Hamiltonian Chromatic Number of Trees

Devsi Bantva

Department of MathematicsLukhdhirji Engineering College, MorviGujarat (INDIA)E-mail: [e-mail]

S. K. Vaidya

Department of MathematicsSaurashtra University,Rajkot, Gujarat (INDIA)E-mail: [e-mail]

Let G be a simple finite connected graph of order n. The detour distance between two distinct vertices u and v denoted by D(u, v) is the length of a longest uv-path in G. A hamiltonian coloring h of a graph G of order n is a mapping h : V(G) → {0, 1, 2, …} such that D(u, v) + |h(u) − h(v)| ≥ n − 1, for every two distinct vertices u and v of G. The span of h, denoted by span(h), is max{|h(u) − h(v)| : u, v ∈ V(G)}. The hamiltonian chromatic number of G is defined as