• 主题
高级搜索  >
历史搜索 清空历史
首页> 美国政府科技报告 >Note on a Conjecture Concerning Tree-Partitioning 3-Regular Graphs
【24h】

Note on a Conjecture Concerning Tree-Partitioning 3-Regular Graphs

机译：关于树分割3正则图的猜想的注记

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

If G is a 4-connected maximal planar graph, then G is hamiltonian (by a theorem211u001eof Whitney), implying that its dual graph G(sup star) is a cyclically 4-edge 211u001econnected 3-regular planar graph admitting a partition of the vertex set into two 211u001eparts, each inducing a tree in G(sup star), a so-called tree-partition. It is a 211u001enatural question whether each cyclically 4-edge connected 3-regular graph admits 211u001esuch a tree-partition. This was conjectured by Jaeger, and recently independently 211u001eby the first author. The main result of this note shows that each connected 3-211u001eregular graph on n vertices admits a partition of the vertex set into two sets 211u001esuch that precisely (1/2)n + 2 edges edges have end vertices in each set. This is 211u001ea necessary condition for having a tree-partition. The authors also show that not 211u001eall cyclically 3-edge connected 3-regular (planar) graphs admit a tree-partition, 211u001eand present the smallest counterexamples.

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号