• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >The treewidth of line graphs
【24h】

The treewidth of line graphs

机译：线宽的线图

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

摘要

The treewidth of a graph is an important invariant in structural and algorithmic graph theory. This paper studies the treewidth of line graphs. We show that determining the treewidth of the line graph of a graph G is equivalent to determining the minimum vertex congestion of an embedding of G into a tree. Using this result, we prove sharp lower bounds in terms of both the minimum degree and average degree of G. These results are precise enough to exactly determine the treewidth of the line graph of a complete graph and other interesting examples. We also improve the best known upper bound on the treewidth of a line graph. Analogous results are proved for pathwidth. (C) 2018 Elsevier Inc. All rights reserved.
机译：图形的树宽是结构和算法图论中的重要不变。 本文研究了线条图的树木。 我们示出了确定图G的线图的树宽等同于确定G进入树的最小顶点拥塞。 使用此结果，我们在G的最小程度和平均程度方面证明了急剧下限。这些结果精确地足够精确地确定完整图和其他有趣的例子的线图的树宽。 我们还改善了线条图树木的最佳已知的上限。 证明了普遍的结果。 （c）2018年Elsevier Inc.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号