• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Complexity of (p, 1)-total labelling
【24h】

Complexity of (p, 1)-total labelling

机译：（p，1）-总标记的复杂度

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A (p, 1)-total labelling of a graph G = (V, E) is a total colouring L from V boolean OR E into {0,...,l} such that vertical bar L(v) - L(e)vertical bar >= p whenever an edge e is incident to a vertex v. The minimum l for which G admits a (p, 1)-total labelling is denoted by lambda(p)(G). The case p = 1 corresponds to the usual notion of total colouring, which is NP-hard to compute even for cubic bipartite graphs [C.J. McDiarmid, A. Sanchez-Arroyo, Total colouring regular bipartite graphs is NP-hard, Discrete Math. 124 (1994). 155-162]. In this paper we assume p >= 2. It is easy to show that lambda(p)(G) >= Delta + p - 1, whered Delta is the maximum degree of G. Moreover, when G is bipartite, Delta + p is an upper bound for lambda(p)(G), leaving only two possible values. In this paper, we completely settle the computational complexity of deciding whether lambda(p)(G) is equal to Delta + p - 1 or to Delta + p when G is bipartite. This is trivial when Delta <= p, polynomial when Delta = 3 and p = 2, and NP-complete in the remaining cases.
机译：图G =（V，E）的（p，1）-总标记是从V布尔OR E到{0，...，l}的总着色L，使得竖线L（v）-L（ e）每当边缘e入射到顶点v时，竖线> =p。G允许总标记为（p，1）的最小值l用lambda（p）（G）表示。 p = 1的情况对应于总着色的通常概念，即使对于立方二分图，这也是NP难以计算的。 McDiarmid，A。Sanchez-Arroyo，总着色规则二分图是NP-hard，离散数学。 124（1994）。 155-162]。在本文中，我们假设p> =2。很容易证明lambda（p）（G）> = Delta + p-1，其中Delta是G的最大程度。而且，当G为二分时，Delta + p是lambda（p）（G）的上限，仅保留两个可能的值。在本文中，我们完全解决了确定G是二分式时lambda（p）（G）等于Delta + p-1还是等于Delta + p的计算复杂性。当Delta <= p时，这是微不足道的;当Delta = 3且p = 2时，是多项式的;在其余情况下，NP完全。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号