New comments on A Hamilton sufficient condition for completely independent spanning tree

For k >= 2, spanning trees T-1, T-2,..., T-k in a graph G are called to be completely independent if for any two distinct vertices x and y, the paths connecting them in T-1, T-2,..., T-k are pairwise openly disjoint. We call such spanning trees T-1, T-2,..., T-k the completely independent spanning trees (CIST for short). Recently, Hong and Zhang (2020) found that a sufficient condition for Hamiltonian graphs also suffices the existence of two CISTs. That is, if G is a graph with n vertices, vertical bar N(x) boolean OR N(y)vertical bar >= n/2 and vertical bar N(x) boolean AND N(y)vertical bar >= 3 for every two non-adjacent vertices x, y of G and n >= 5, then G has two CISTs. More recently, Qin et al. (2020) proposed that the restriction on the number of vertices in the statement should be n >= 8, and then pointed out that the Claim 1 in Hong's paper is not always true for general case, which was corrected by presenting an amendment. However, there still exists a flaw in the corresponding revised proof (see details from the second part of our paper). Accordingly, we give a new amendment to correct the proof. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

This paper introduces the concept of completely independent spanning trees and discusses the existence of two CISTs under certain conditions, as well as different views on the number of vertices in the theorem statement.