Completely independent spanning trees in some Cartesian product graphs

Abstract

Let $ T_{1}, T_{2}, \dots, 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}, \dots, 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}\Box P_{n}, \ W_{m}\Box C_{n}, \ K_{m, n}\Box P_{r}, \ K_{m, n}\Box C_{r}, \ K_{m, n, r}\Box P_{s}, \ K_{m, n, r}\Box C_{s} $.

Keywords

• completely independent spanning tree
• cartesian product graph
• path
• cycle
• wheel
• complete bipartite graph
• complete tripartite graph