pith. sign in

arxiv: 2606.12827 · v1 · pith:2ZNM2W26new · submitted 2026-06-11 · 🧮 math.CO · cs.DM

Completely Independent Spanning Trees in k-Outerplanar Triangulated Discs

Toru Araki This is my paper

Pith reviewed 2026-06-27 06:50 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords completely independent spanning treesouterplanar graphstriangulated discsspanning treesplanar graphsgraph connectivity
0
0 comments X

The pith

Every 3-connected 2-outerplanar triangulated disc contains two completely independent spanning trees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that every 3-connected 2-outerplanar triangulated disc has two completely independent spanning trees. These trees are defined so that the paths they induce between any pair of vertices share no internal vertices. A sympathetic reader would care because the property supplies multiple vertex-disjoint routes, which supports reliable routing in networks that can be drawn as such discs. The work also states sufficient conditions under which 3-outerplanar triangulated discs possess two such trees and exhibits a 3-connected 4-outerplanar triangulation without them.

Core claim

We first prove that every 3-connected 2-outerplanar triangulated disc has two completely independent spanning trees. Next, for a 3-connected 3-outerplanar triangulated disc G, we provide sufficient conditions for G to have two completely independent spanning trees. We provide an example of a 3-connected 4-outerplanar triangulation that does not have two completely independent spanning trees.

What carries the argument

Completely independent spanning trees, defined as a collection of spanning trees in which the paths between any vertex pair are pairwise openly disjoint.

If this is right

  • Every 3-connected 2-outerplanar triangulated disc admits at least two completely independent spanning trees.
  • Sufficient conditions on 3-outerplanar triangulated discs guarantee the existence of two completely independent spanning trees.
  • There exist 3-connected 4-outerplanar triangulations that admit no pair of completely independent spanning trees.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The outerplanarity index appears to mark a transition point beyond which the existence of two CISTs can fail even under 3-connectivity.
  • The structural proofs may adapt to other bounded-outerplanarity families that remain triangulated and 3-connected.
  • The counterexample construction could be generalized to produce families without two CISTs for any outerplanarity index at least four.

Load-bearing premise

The input graphs must be 3-connected triangulated discs; the existence guarantee need not hold if connectivity or triangulation is relaxed.

What would settle it

A single 3-connected 2-outerplanar triangulated disc in which no pair of spanning trees has openly disjoint paths between every vertex pair would falsify the main theorem.

Figures

Figures reproduced from arXiv: 2606.12827 by Toru Araki.

Figure 1
Figure 1. Figure 1: The situation of Case 2 of Theorem 3.1. Some edges joining vertices of [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An example of a 2-connected 2-outerplanar triangulated disc [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: (Left) An example of a striped 1-outerplanar triangulated disc for Lemma 3.2. [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The situation of (a) Case 1 and (b) Case 2 of Lemma 4.1. The black and [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A 3-connected 3-outerplanar graph G that has a CIST-partition (V1, V2). The sets of black and white vertices are members of V1 and V2, respectively. The subgraph G2 = G[L1 ∪ L2] is isomorphic to the graph shown in [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Tutte graph G. the following theorem. Theorem 5.1. There exists a 3-connected triangulated disc with a 4-outerplanar em￾bedding that does not have two completely independent spanning trees. 6 Conclusion Hasunuma [8] proved that every 4-connected plane triangulation has two CISTs. Later, P´eterfalvi [17] pointed out that a 3-connected plane triangulation with no CISTs exists. In this paper, we investigate t… view at source ↗
Figure 7
Figure 7. Figure 7: The dual of Tutte graph G∗ . References [1] T. Araki, Dirac’s condition for completely independent spanning trees, Journal of Graph Theory 77 (3) (2014) 171–179. doi:10.1002/jgt.21780 [2] T. Araki, M. Matsushita, Y. Otachi, Completely independent spanning trees in (partial) k-trees, Discussiones Mathematicae Graph Theory 35 (2015) 427–437. doi:10.7151/dmgt.1806 [3] Y.-H. Chang, K.-J. Pai, C.-C. Hsu, J.-S. … view at source ↗
Figure 8
Figure 8. Figure 8: The graph DG that is made from the Tutte graph. The gray vertices are the vertices added to the dual G∗ to construct DG. This graph does not have two completely independent spanning trees. We can see that this embedding is 4-outerplanar. 14 [PITH_FULL_IMAGE:figures/full_fig_p014_8.png] view at source ↗
read the original abstract

Let $T_{1}, T_{2}, \dots, T_{k}$ be $k$ spanning trees of a graph $G$. For any pair of vertices $u$ and $v$, if the $u$--$v$ paths in the $k$ spanning trees are pairwise openly disjoint, then the spanning trees are called completely independent spanning trees (CISTs) of $G$. In this paper, we first prove that every 3-connected 2-outerplanar triangulated disc has two completely independent spanning trees. Next, for a 3-connected 3-outerplanar triangulated disc $G$, we provide sufficient conditions for $G$ to have two completely independent spanning trees. We provide an example of a 3-connected 4-outerplanar triangulation that does not have two completely independent spanning trees.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper proves that every 3-connected 2-outerplanar triangulated disc has two completely independent spanning trees. For 3-connected 3-outerplanar triangulated discs it supplies sufficient conditions for the existence of two CISTs, and it exhibits an explicit 3-connected 4-outerplanar triangulation that admits no such pair.

Significance. The results delineate the range of outerplanarity parameters for which the CIST property is guaranteed under 3-connectivity and triangulation, supplying both a positive structural theorem for k=2 and a concrete negative instance for k=4. The explicit counterexample construction is a concrete strength.

minor comments (2)
  1. [Abstract] The abstract states that proofs and a counterexample exist but supplies no indication of the proof technique, key lemmas, or structural decomposition used; adding a one-sentence outline of the argument would improve readability without lengthening the abstract.
  2. The definition of completely independent spanning trees is given only in the abstract; repeating the definition (or a concise reference to it) at the start of the main technical section would aid readers who begin reading from the introduction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of our results on completely independent spanning trees in outerplanar triangulated discs. The recommendation for minor revision is noted; however, no specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents direct existence proofs for two completely independent spanning trees in 3-connected 2-outerplanar triangulated discs, sufficient conditions for the 3-outerplanar case, and an explicit counterexample for 4-outerplanar graphs. No equations, fitted parameters, or statistical predictions appear. The central claims rest on structural hypotheses (3-connectivity and triangulation) that are explicitly stated in the theorem statements rather than derived from the conclusions. No self-citation chains, ansatzes smuggled via prior work, or renamings of known results are load-bearing in the provided abstract and description. The derivation is self-contained via graph-theoretic constructions and counterexample, with no reduction of outputs to inputs by definition.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Claims rest on the standard definitions of spanning trees, outerplanarity, triangulation, and 3-connectivity together with the definition of openly disjoint paths; no additional free parameters or invented entities are introduced.

axioms (1)
  • standard math Standard axioms and definitions of finite undirected graphs, spanning trees, k-outerplanarity, triangulation, and vertex-connectivity.
    Invoked throughout the statements of the three main results.

pith-pipeline@v0.9.1-grok · 5665 in / 1157 out tokens · 31283 ms · 2026-06-27T06:50:17.144179+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

19 extracted references · 12 canonical work pages

  1. [1]

    Araki, Dirac’s condition for completely independent spanning trees, Journal of Graph Theory 77 (3) (2014) 171–179

    T. Araki, Dirac’s condition for completely independent spanning trees, Journal of Graph Theory 77 (3) (2014) 171–179. doi:10.1002/jgt.21780

    work page doi:10.1002/jgt.21780 2014

  2. [2]

    Araki, M

    T. Araki, M. Matsushita, Y. Otachi, Completely independent spanning trees in (partial) k-trees, Discussiones Mathematicae Graph Theory 35 (2015) 427–437. doi:10.7151/dmgt.1806

    work page doi:10.7151/dmgt.1806 2015

  3. [3]

    Chang, K.-J

    Y.-H. Chang, K.-J. Pai, C.-C. Hsu, J.-S. Yang, J.-M. Chang, Constructing dual- CISTs of folded divide-and-swap cubes, Theoretical Computer Science 856 (2021) 75–87. doi:10.1016/j.tcs.2020.12.023

    work page doi:10.1016/j.tcs.2020.12.023 2021

  4. [4]

    G. Chen, B. Cheng, D. Wang, Constructing completely independent spanning trees in data center network based on augmented cube, IEEE Transactions on Parallel and Distributed Systems 32 (3) (2021) 665–673

    2021

  5. [5]

    X. Chen, Q. Liu, X. Yang, Two completely independent spanning trees of split graphs, Discrete Applied Mathematics 340 (2023) 76–78. doi:10.1016/j.dam.2023.07.001 13 Figure 8: The graphD G that is made from the Tutte graph. The gray vertices are the vertices added to the dualG ∗ to constructD G. This graph does not have two completely independent spanning ...

    work page doi:10.1016/j.dam.2023.07.001 2023

  6. [6]

    Cheng, D

    B. Cheng, D. Wang, J. Fan, Independent spanning trees in networks: A survey, ACM Comput. Surv. 55 (14s). doi:10.1145/3591110

    work page doi:10.1145/3591110

  7. [7]

    Hasunuma, Completely independent spanning trees in the underlying graph of a line digraph, Discrete Mathematics 234 (2001) 149–157

    T. Hasunuma, Completely independent spanning trees in the underlying graph of a line digraph, Discrete Mathematics 234 (2001) 149–157

    2001

  8. [8]

    T. Hasunuma, Completely independent spanning trees in maximal planar graphs, in: Proceedings of 28th Graph Theoretic Concepts of Computer Science (WG2002), LNCS 2573, Springer-Verlag Berlin, 2002, pp. 235–245

    2002

  9. [9]

    Hasunuma, Minimum degree conditions and optimal graphs for completely in- dependent spanning trees, in: Z

    T. Hasunuma, Minimum degree conditions and optimal graphs for completely in- dependent spanning trees, in: Z. Lipt´ ak, W. F. Smyth (eds.), Combinatorial Al- gorithms, Springer International Publishing, Cham, 2016

    2016

  10. [10]

    Hasunuma, Completely independent spanning trees in line graphs, Graphs and Combinatorics 39 (2023) 90

    T. Hasunuma, Completely independent spanning trees in line graphs, Graphs and Combinatorics 39 (2023) 90. doi:10.1007/s00373-023-02688-y

    work page doi:10.1007/s00373-023-02688-y 2023

  11. [11]

    Hasunuma, C

    T. Hasunuma, C. Morisaka, Completely independent spanning trees in torus net- works, Networks 60 (2012) 59–69. doi:10.1002/net.20460

    work page doi:10.1002/net.20460 2012

  12. [12]

    X. Hong, H. Zhang, A Hamilton sufficient condition for completely independent spanning tree, Discrete Applied Mathematics 279 (2020) 183–187

    2020

  13. [13]

    X. Hong, Z. Zhang, Completely independent spanning trees inkth power of 2-connected graphs, Discrete Applied Mathematics 372 (2025) 268–273. doi:10.1016/j.dam.2025.04.051

    work page doi:10.1016/j.dam.2025.04.051 2025

  14. [14]

    Pai, R.-S

    K.-J. Pai, R.-S. Chang, J.-M. Chang, Constructing dual-CISTs of pancake graphs and performance assessment of protection routings on some Cayley networks, J. Supercomput. 77 (1) (2021) 990–1014. doi:10.1007/s11227-020-03297-9

    work page doi:10.1007/s11227-020-03297-9 2021

  15. [15]

    Pai, S.-M

    K.-J. Pai, S.-M. Tang, J.-M. Chang, J.-S. Yang, Completely independent spanning trees on complete graphs, complete bipartite graphs and complete tripartite graphs, in: R.-S. Chang, L. C. Jain, S.-L. Peng (eds.), Advances in Intelligent Systems and Applications - Volume 1, Springer Berlin Heidelberg, Berlin, Heidelberg, 2013

    2013

  16. [16]

    Pai, J.-S

    K.-J. Pai, J.-S. Yang, G.-Y. Chen, J.-M. Chang, Configuring protection routing via completely independent spanning trees in dense Gaussian on-chip networks, IEEE Transactions on Network Science and Engineering 9 (2) (2022) 932–946. 15

    2022

  17. [17]

    P´ eterfalvi, Two counterexamples on completely independent spanning trees, Discrete Mathematics 312 (2012) 808–810

    F. P´ eterfalvi, Two counterexamples on completely independent spanning trees, Discrete Mathematics 312 (2012) 808–810. doi:10.1016/j.disc.2011.11.015

    work page doi:10.1016/j.disc.2011.11.015 2012

  18. [18]

    M. Wang, R. Liu, A note on the 4-connected line graph of a planar triangulation containing two CISTs, Graphs and Combinatorics 42, 5(2026). doi:10.1007/s00373- 025-03002-8

    work page doi:10.1007/s00373- 2026

  19. [19]

    J. Yuan, J. Hao, A. Liu, S. Chai, S. Lin, The completely independent span- ning trees inP 4-free graphs, Discrete Applied Mathematics 377 (2025) 573–585. doi:10.1016/j.dam.2025.08.048 16

    work page doi:10.1016/j.dam.2025.08.048 2025