论文标题
笛卡尔产品的距离标记
Distance-constrained labellings of Cartesian products of graphs
论文作者
论文摘要
a $ l（h_1，h_2，\ ldots，h_l）$ - 图$ g $的标签是映射$ ϕ：v（g）\ rightArrow \ {0，1，2，\ ldots \} $，以便以$ 1 \ le i \ le l $和$ g $ u， ϕ（v）| \ geq h_i $。 $ ϕ $的跨度是分配给$ g $的最大和最小标签，$ g $ by $ ϕ $，$λ_{h_1，h_2，h_2，\ ldots，h_l}（g）$定义为所有$ l（H_1，H_1，H_2，H_2，H_2，\ ldots $ ldots $ ldots $ ldots $ g $ g $ g $ g $ g $ g $。 在本文中，我们研究$λ_{h，1，\ ldots，1} $用于笛卡尔的图形产品，其中$（h，1，\ ldots，1）$是$ l $ tuple，带有$ l \ ge 3 $。我们证明，在某些自然条件下，该图$ h $的价值和三个相关的不变性，这是$ l $图的笛卡尔产品，达到了一个共同的下限。特别是，$ h $的$ l $ th功率的色数等于此下限加一个。我们进一步获得了将结果扩展到$ h $的子图的一家子图，其中包含$ h $ $ h $的子图。所有这些结果尤其适用于锤态图：如果$ q_1 \ ge \ cdots \ ge q_d \ ge 2 $和$ 3 \ le l \ le d $，则hamming图$ h = h_ = h_ {q_1，q_1，q_2，q_2，\ ldots，q_d} $ q_1q_2 \ ldots q_l-1 $每当$ q_1q_2 \ ldots q_ {l-1}> 3（q_ {l-1} +1）q_l \ ldots q_d $。特别是，这解决了一个在色皮的色素幂数上的开放问题的情况。
An $L(h_1, h_2, \ldots, h_l)$-labelling of a graph $G$ is a mapping $ϕ: V(G) \rightarrow \{0, 1, 2, \ldots\}$ such that for $1\le i\le l$ and each pair of vertices $u, v$ of $G$ at distance $i$, we have $|ϕ(u) - ϕ(v)| \geq h_i$. The span of $ϕ$ is the difference between the largest and smallest labels assigned to the vertices of $G$ by $ϕ$, and $λ_{h_1, h_2, \ldots, h_l}(G)$ is defined as the minimum span over all $L(h_1, h_2, \ldots, h_l)$-labellings of $G$. In this paper we study $λ_{h, 1, \ldots, 1}$ for Cartesian products of graphs, where $(h, 1, \ldots, 1)$ is an $l$-tuple with $l \ge 3$. We prove that, under certain natural conditions, the value of this and three related invariants on a graph $H$ which is the Cartesian product of $l$ graphs attain a common lower bound. In particular, the chromatic number of the $l$-th power of $H$ equals this lower bound plus one. We further obtain a sandwhich theorem which extends the result to a family of subgraphs of $H$ which contain a certain subgraph of $H$. All these results apply in particular to the class of Hamming graphs: if $q_1\ge \cdots \ge q_d\ge 2$ and $3\le l\le d$ then the Hamming graph $H=H_{q_1,q_2,\ldots ,q_d}$ satisfies $λ_{q_l,1,\ldots,1}(H) = q_1q_2\ldots q_l-1$ whenever $q_1q_2\ldots q_{l-1}>3(q_{l-1}+1)q_l\ldots q_d$. In particular, this settles a case of the open problem on the chromatic number of powers of the hypercubes.
