Scholarlink

<p>The 3-decomposition conjecture states that every connected cubic graph can be decomposed into a spanning tree, a union of cycles, and a matching. In this paper, we use a rooted spanning tree as a tool to show that every connected cubic graph of size <i>n</i> can be decomposed into a spanning tree, a union of cycles, a matching, and a union of at most <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\({{n-4} \over 8}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mfrac> <mrow> <mi>n</mi> <mo>−</mo> <mn>4</mn> </mrow> <mn>8</mn> </mfrac> </mrow> </math></EquationSource> </InlineEquation> paths of length 2.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

The 3-decomposition conjecture of cubic graphs

  • 期刊论文

  • 发表日期：

    2026年3月13日

查看全文
  • Genghua Fan,
  • Shanshan Guo,
  • Chuixiang Zhou

摘要

The 3-decomposition conjecture states that every connected cubic graph can be decomposed into a spanning tree, a union of cycles, and a matching. In this paper, we use a rooted spanning tree as a tool to show that every connected cubic graph of size n can be decomposed into a spanning tree, a union of cycles, a matching, and a union of at most \({{n-4} \over 8}\) n − 4 8 paths of length 2.