论文标题
汉密尔顿色的树木数
Hamiltonian chromatic number of trees
论文作者
论文摘要
令$ g $为订单$ n $的简单有限连接图。 $ d（u，v）$表示的两个不同的顶点$ u $和$ v $之间的弯路距离是$ g $中最长的$ uv $ path的长度。 agraltonian着色$ h $ a Graph $ g $ ford $ n $是映射$ h：v（g）\ rightarrow \ {0,1,2，... \} $，因此$ d（u，v） + | h（u） + | h（u）-h（u）-h（v）| \ geq n-1 $，对于每两个不同的顶点$ u $和$ g $的$ v $。 $ h $的跨度为$ span（h）$，为$ \ max \ {| h（u）-h（v）| ：u，v \ in V（g）\} $。 $ g $的汉密尔顿色数定义为$ hc（g）：= \ min \ {span（h）\} $，最低占所有汉密尔顿着色$ h $ g $ $ g $。在本文中，我们为哈密顿色的树木数量提供了改进的下限，并提供了必要和足够的条件以实现改进的下限。使用此结果，我们确定了两个树木家族的汉密尔顿色素数。
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) \rightarrow \{0,1,2,...\}$ such that $D(u,v) + |h(u)-h(v)| \geq 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 \in V(G)\}$. The hamiltonian chromatic number of $G$ is defined as $hc(G) := \min\{span(h)\}$ with minimum taken over all hamiltonian coloring $h$ of $G$. In this paper, we give an improved lower bound for the hamiltonian chromatic number of trees and give a necessary and sufficient condition to achieve the improved lower bound. Using this result, we determine the hamiltonian chromatic number of two families of trees.
