Scholarlink

<p>Completely independent spanning trees (CISTs) in a graph <i>G</i> are spanning trees of <i>G</i> such that for any two distinct vertices of <i>G</i>, the paths between them in the spanning trees are pairwise edge-disjoint and internally vertex-disjoint. Hasunuma proved that there are two CISTs in any 4-connected planar triangulation and asked whether every 4-connected planar graph contains two CISTs. In this paper, we give a negative answer to this question and prove that every 4-connected line graph of a planar triangulation contains two CISTs.</p>

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

A Note on the 4-Connected Line Graph of a Planar Triangulation Containing Two CISTs

  • 期刊论文

  • 发表日期：

    2025年12月15日

查看全文
  • Maoqun Wang,
  • Ruhua Liu

摘要

Completely independent spanning trees (CISTs) in a graph G are spanning trees of G such that for any two distinct vertices of G, the paths between them in the spanning trees are pairwise edge-disjoint and internally vertex-disjoint. Hasunuma proved that there are two CISTs in any 4-connected planar triangulation and asked whether every 4-connected planar graph contains two CISTs. In this paper, we give a negative answer to this question and prove that every 4-connected line graph of a planar triangulation contains two CISTs.