Publications
Sort:
Open Access Research Article Issue
Completely independent spanning trees in some Cartesian product graphs
AIMS Mathematics 2023, 8(7): 16127-16136
Published: 15 July 2023
Abstract PDF (479.9 KB) Collect
Downloads:0

Let T 1 , T 2 , , T k be spanning trees of a graph G. For any two vertices u , v of G, if the paths from u to v in these k trees are pairwise openly disjoint, then we say that T 1 , T 2 , , T k are completely independent. Hasunuma showed that there are two completely independent spanning trees in any 4-connected maximal planar graph, and that given a graph G, the problem of deciding whether there exist two completely independent spanning trees in G is NP-complete. In this paper, we consider the number of completely independent spanning trees in some Cartesian product graphs such as W m P n , W m C n , K m , n P r , K m , n C r , K m , n , r P s , K m , n , r C s .

Total 1