REVIEW 2 cited by
Fan's condition for completely independent spanning trees
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
Spanning trees $T_1,T_2, \dots,T_k$ of $G$ are $k$ completely independent spanning trees if, for any two vertices $u,v\in V(G)$, the paths from $u$ to $v$ in these $k$ trees are pairwise edge-disjoint and internal vertex-disjoint. Hasunuma proved that determining whether a graph contains $k$ completely independent spanning trees is NP-complete, even for $k = 2$. Araki posed the question of whether certain known sufficient conditions for hamiltonian cycles are also also guarantee two completely independent spanning trees? In this paper, we affirmatively answer this question for the Fan-type condition. Precisely, we proved that if $G$ is a connected graph such that each pair of vertices at distance 2 has degree sum at least $|V(G)|$, then $G$ has two completely independent spanning trees.
Forward citations
Cited by 2 Pith papers
-
Constructing two completely independent spanning trees in the dual-cube
For every n ≥ 5, the n-dimensional dual-cube contains two completely independent spanning trees; for n ≥ 6 the paper gives a recursive construction with diameter bounds 5n+5 and 5n+7.
-
Completely Independent Spanning Trees in Split Graphs: Structural Properties and Complexity
A split graph has k completely independent spanning trees roughly when its associated hypergraph admits a bipanchromatic k-coloring; deciding the case k=2 is NP-complete.
Discussion (0). Continue with ORCID to comment.