...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >On hypercube labellings and antipodal monochromatic paths
【24h】

On hypercube labellings and antipodal monochromatic paths

机译：关于超立方体标记和对映单色路径

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

摘要

A labelling of the n-dimensional hypercube H_n is a mapping that assigns value 0 or 1 to each edge of H_n. A labelling is antipodal if antipodal edges of H_n get assigned different values. It has been conjectured that, if H_n,n≥2, is given a labelling that is antipodal, then there exists a pair of antipodal vertices joined by a monochromatic path. This conjecture has been verified by hand for n≤5. In this paper, we verify the conjecture in the case where the labelling is simple in the sense that no square xyzt in H_n has value 0 assigned to xy,zt and value 1 assigned to yz,tx, even if the given labelling is not antipodal. The proof is based on a new property of (not necessarily antipodal) simple labellings of H_n. We also exhibit a large class of simple labellings that thus satisfy the conjecture. Finally, we conjecture that, even if the given labelling is not antipodal, there is always a path joining antipodal vertices that switches labels at most once, which implies the original conjecture. We establish this new conjecture for H_n,n≤5 as well.
机译：n维超立方体H_n的标签是将值0或1分配给H_n的每个边的映射。如果为H_n的对映边分配了不同的值，则标记为对映。可以推测，如果H_n，n≥2，被赋予对映体标记，则存在一对由单色路径相连的对映体顶点。手动验证了n≤5的猜想。在本文中，我们证明了在标签简单的情况下的猜想，即即使给定的标签不是对偶的，H_n中没有正方形xyzt的值0分配给xy，zt且值1分配给yz，tx 。该证明基于H_n的简单标记（不一定是对立的）的新属性。我们还展示了一大类简单的标签，因此可以满足猜想。最后，我们推测，即使给定的标签不是对立的，也总是存在连接对立顶点的路径，该路径最多切换一次标签，这暗示了原始的猜想。我们也为H_n，n≤5建立了这个新的猜想。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号