Completely independent spanning trees in some Cartesian product graphs

1.   Introduction

The graphs considered in this paper are finite, undirected, and simple (no loops or multiple edges). The vertex set and the edge set of $ G $ are denoted by $ V(G) $ and $ E(G) $, respectively. For a vertex $ v\in V(G) $, the neighbor set $ N_{G}(v) $ is the set of vertices adjacent to $ v $, $ d_G(v) = |N_G(v)| $ is the degree of $ v $. For a subgraph $ H $ of $ G $, $ N_{H}(v) $ is the set of the neighbours of $ v $ which are in $ H $, and $ d_H(v) = |N_H(v)| $ is the degree of $ v $ in $ H $. When no confusion arises, we shall write $ N(v) $ and $ d(v) $, instead of $ N_{G}(v) $ and $ d_G(v) $.

is the minimum degree of $ G $. For a subset $ U\subseteq V(G) $, the subgraph induced by $ U $ is denoted by $ G[U] $, which is the graph on $ U $ whose edges are precisely the edges of $ G $ with both ends in $ U $.

A tree $ T $ of $ G $ is a spanning tree of $ G $ if $ V(T) = V(G) $. A leaf is a vertex of degree 1. An internal vertex is a vertex of degree at least 2. A wheel graph $ W_{m} $ is a graph with $ m(m\geq 4) $ vertices, formed by connecting a single vertex $ u_{0} $ to all vertices of cycle $ C_{m-1} = u_{1}u_{2}\cdots u_{m-1} $. Its vertex set is $ \{u_{0}, u_{1}, \cdots, u_{m-1}\} $ and edge set $ \{u_{0}u_{i}, u_{i}u_{i+1(mod\; m-1)}| 1\leq i\leq m-1\} $. We called $ u_{0} $ is a center and $ u_{0}u_{i}(1\leq i\leq m-1) $ is a spoke. A graph $ G $ is a complete $ k $-partite graph if there is a partition $ V_{1}\cup\cdots \cup V_{k} $ of the vertex set $ V(G) $, such that $ uv\in E(G) $ if and only if $ u $ and $ v $ are in different parts of the partition. If $ |V_{i}| = n_{i}(1\leq i\leq k) $, then $ G $ is denoted by $ K_{n_{1}, \cdots, {n_{k}}} $. Particularly, if $ k = 2, 3 $, then call it a complete bipartite graph and complete tripartite graph, respectively. Denote $ P_{n} $ and $ C_{n} $ to be path and cycle with $ n $ vertices. Given two graphs $ G $ and $ H $, the Cartesian product of $ G $ and $ H $, denoted by $ G\Box H $, is the graph with vertex set

and edge set

Let $ x, y $ be two vertices of $ G $. An $ (x, y) $-path is a path with the two ends $ x $ and $ y $. Two $ (x, y) $-paths $ P_{1} $, $ P_{2} $ are openly disjoint if they have no common edge and no common vertex except for the two ends $ x $ and $ y $. Let $ T_{1}, T_{2}, \dots, T_{k} $ be spanning trees in a graph $ G $. If for any two vertices $ u, v $ of $ G $, the paths from $ u $ to $ v $ in $ T_{1}, T_{2}, \dots, T_{k} $ are pairwise openly disjoint, then we say that $ T_{1}, T_{2}, \dots, T_{k} $ are completely independent spanning trees (CISTs) in $ G $. The concept of completely independent spanning trees (CISTs) was proposed by Hasunuma ^[6] and he gave a characterization for CISTs. It can be seen from the definition that a completely independent spanning tree is an independent spanning tree rooted at any vertex. That is to say, in the study of fault-tolerant broadcasting problems in parallel computing, if we construct a completely independent spanning tree, then when the source vertex becomes any other vertex, there is no need to re-construct the independent spanning tree. In fact, completely independent spanning trees have been studied from not only the theoretical point of view but also the practical point of view because of their applications to fault-tolerant broadcasting in parallel computers ^[14].

It is well known ^[16] that every $ 2k $-edge-connected graph has $ k $ edge-disjoint spanning trees. Similarly, Hasunuma ^[7] conjectured that every $ 2k $-connected graph has $ k $ CISTs. Ten years later, Péterfalvi ^[18] disproved the conjecture by constructing a $ k $-connected graph, for each $ k\geq 2 $, which does not have two CISTs. Based on the question raised by Araki ^[1], in recent years, a specific relationship has been given between Hamilton's sufficient condition and the existence of a completely independent spanning tree, such as Fleischner's condition ^[1], Dirac's condition ^[1], Ore's condition ^[5] and Neighborhood union and intersection condition ^[13]. Moreover, the Dirac's condition has been generalized to $ k(\geq 2) $ completely independent spanning trees ^[3,9,10] and has been independently improved ^[9,10] for two completely independent spanning trees. Yuan et al. ^[20] show that a degree condition for the existence of $ k $ CISTs in bipartite graphs. Wang et al. ^[19] established the number of CISTs that can be constructed in the line graph of the complete graph. Chen et al. ^[4] proved that if $ G $ is a $ \{claw, hourglass, P_{6}^{2}\} $-free graph with $ \delta(G)\geq 4 $, then $ G $ contains two CISTs if and only if $ cl(G) $ has two CISTs. For the result of completely independent spanning trees in the $ k $-th power graph, see ^[11,12]. In ^[7], it has been proved that it is NP-complete to find the number of completely independent spanning trees for a general graph. Therefore, it is meaningful to study the existence of completely independent spanning trees for special graphs. In ^[8], Hasunuma showed that there are two completely independent spanning trees in the Cartesian product $ C_{m}\Box C_{n} $ for all $ m\geq 3, n\geq 3 $. Also, Masayoshi ^[15] considered the number of completely independent spanning trees in any $ k $-trees. 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} $.

2.   Preliminaries

Definition 2.1. (^[6]) Let $ T_{1}, T_{2}, \dots, T_{k} $ be spanning trees in a graph $ G $. If for any two vertices $ u, v $ of $ G $, the paths from $ u $ to $ v $ in $ T_{1}, T_{2}, \dots, T_{k} $ are pairwise openly disjoint, then we say that $ T_{1}, T_{2}, \dots, T_{k} $ are completely independent spanning trees(CISTs) in $ G $.

Given a graph $ G $, let mcist(G) be the maximum integer $ k $ such that there exist $ k $ completely independent spanning trees in $ G $. The following result obtained by Hasunuma ^[6] plays a key role in our proof.

Lemma 2.1. (^[6]) Let $ k\geq 2 $ be an integer. $ T_{1}, T_{2}, \cdots, T_{k} $ are completely independent spanning trees in a graph $ G $ if and only if they are edge disjoint spanning trees of $ G $ and for any $ v\in V(G) $, there is at most one $ T_{i} $ such that $ d_{T_{i}}(v) > 1 $.

It is easy to see from the lemma that there are two completely independent spanning trees in the following graph as Figure 1.

Lemma 2.2. (^[7]) There are two completely independent spanning trees in any 4-connected maximal plane graph.

Pai et al. ^[17] showed that the following results.

Lemma 2.3. (^[17]) There are $ \lfloor\frac{n}{2}\rfloor $ completely independent spanning trees in complete graph $ K_{n} $ for all $ n\geq 4 $.

Lemma 2.4. (^[17]) There are $ \lfloor\frac{n}{2}\rfloor $ completely independent spanning trees in complete bipartite graph $ K_{m, n} $ for all $ m\geq n\geq 4 $.

Lemma 2.5. (^[17]) There are $ \lfloor\frac{n_{2}+n_{1}}{2}\rfloor $ completely independent spanning trees in complete tripartite graph $ K_{n_{3}, n_{2}, n_{1}} $ for all $ n_{3}\geq n_{2}\geq n_{1} $ and $ n_{2}+n_{1}\geq 4 $.

In 2012, Hasunuma ^[8] showed that the following result holds.

Lemma 2.6. (^[8]) There are two completely independent spanning trees in the Cartesian product of any 2-connected graphs.

Darties ^[2] determined the maximum number of completely independent spanning trees in Cartesian product $ K_{m}\Box C_{n} $.

Lemma 2.7. (^[2]) Let $ m\geq 3 $ and $ n\geq 3 $ be integers. We have

In 2015, Matsushita et al. ^[15] consider the maximum number of completely independent spanning trees in any $ k $-trees and proved the following result.

Lemma 2.8. (^[15]) If $ k\geq 3 $, then $ \lfloor\frac{k+1}{2}\rfloor\leq mcist(G)\leq k-1 $ for any $ k $-trees $ G $.

3.   Main results

Theorem 3.1. Let $ m $ and $ n $ be integers and $ m\geq 4, \ n\geq 2 $. We have

Proof. Denote wheel

and

The Cartesian product $ W_{m}\Box P_{n} $ is denoted by as follows:

Note that

On the one hand, completely independent spanning trees are edge disjoint by Lemma 1 and every spanning tree has $ mn-1 $ edges, and combining with $ m\geq 4, \ n\geq 2 $, we have

On the other hand, we give the lower bound of $ mcist(W_{m}\Box P_{n}) $ by constructing two completely independent spanning trees in $ W_{m}\Box P_{n} $.

We construct two completely independent spanning trees $ T_{1} $, $ T_{2} $ as follows:

and

It is easy to see that $ T_{1} $ and $ T_{2} $ are edge disjoint. Note that the spanning tree $ T_{1} $ contains $ 2n $ internal vertices $ \{u_{0}^{j}, u_{2}^{j}| 0\leq j\leq n-1\} $ which are leaves in $ T_{2} $. And $ T_{2} $ contains $ (m-2)n $ internal vertices $ \{u_{1}^{j}, u_{i}^{j}|3\leq i\leq m-1, 0\leq j\leq n-1\} $ which are leaves in $ T_{1} $. Hence, by Lemma 2, $ T_{1} $ and $ T_{2} $ are two completely independent spanning trees as Figure 2. Therefore, $ mcist(W_{m}\Box P_{n})\geq 2 $ and further we have $ mcist(W_{m}\Box P_{n}) = 2 $.

Corollary 3.1. Let $ m $ and $ n $ be integers and $ m\geq 4, \ n\geq 2 $. We have

Proof. Denote wheel

and

The Cartesian product $ W_{m}\Box C_{n}(n\geq 3) $ is denoted by as follows:

Note that

On the one hand, completely independent spanning trees are edge disjoint by Lemma 2 and every spanning tree has $ mn-1 $ edges, and combining with $ m\geq 4, n\geq 2 $, we have

On the other hand, we give the lower bound of $ mcist(W_{m}\Box C_{n}) $ by constructing two completely independent spanning trees in $ W_{m}\Box C_{n} $. To obtain the lower bound, the construction is similar with Theorem 3.1. Therefore, $ mcist(W_{m}\Box C_{n}) = 2 $.

Theorem 3.2. Let $ m, n, r $ be integers and $ m\geq n\geq 4, \ r\geq 2 $. We have

Proof. Denote $ K_{m, n} $ is complete bipartite graph with

We denote the Cartesian product graphs $ K_{m, n}\Box P_{r} $ and $ K_{m, n}\Box C_{r}(r\geq 3) $ as follows:

Note that

On one hand, completely independent spanning trees are edge disjoint by Lemma 2 and every spanning tree has $ mr+nr-1 $ edges, and combining with $ m\geq n\geq 4, \ r\geq 2 $, we have

On the other hand, we give the lower bound of $ mcist(K_{m, n}\Box P_{r}) $ by constructing $ \lfloor\frac{n}{2}\rfloor $ completely independent spanning trees in $ K_{m, n}\Box P_{r} $.

We construct $ \lfloor\frac{n}{2}\rfloor $ completely independent spanning trees $ T_{1}, \cdots, T_{\lfloor\frac{n}{2}\rfloor} $ as follows:

It is easy to see that $ T_{1}, T_{2}, \cdots, T_{\lfloor\frac{n}{2}\rfloor} $ are edge disjoint. Note that every spanning tree $ T_{i} $ contains $ 4r $ internal vertices $ \{u_{i}^{j}, v_{i}^{j}, u_{\frac{n}{2}+i}^{j}, v_{\frac{n}{2}+i}^{j}| 1\leq j\leq r\} $ which are leaves in $ T_{j}(j\neq i) $. Hence, by Lemma 2, $ T_{1}, T_{2}, \cdots, T_{\lfloor\frac{n}{2}\rfloor} $ are completely independent spanning trees. Therefore, $ mcist(K_{m, n}\Box P_{r})\geq \lfloor\frac{n}{2}\rfloor $ and further it holds. □

An immediate consequence of the above theorem is the following corollary.

Corollary 3.2. Let $ m, n, r $ be integers and $ m\geq n\geq 4, \ r\geq 2 $. We have

Theorem 3.3. Let $ m, n, r $ be integers and $ m\geq n\geq r, \ n+r\geq4 $. We have

Proof. Denote $ K_{m, n, r} $ is complete tripartite graph with

We denote the Cartesian product $ K_{m, n, r}\Box P_{s}(s\geq 3) $ and $ K_{m, n, r}\Box C_{s}(s\geq 3) $ as follows:

Note that

On one hand, completely independent spanning trees are edge disjoint by Lemma 2 and every spanning tree has $ (m+n+r)s-1 $ edges, and combining with $ m\geq n\geq r, n+r\geq4 $, we have

On the other hand, we give the lower bound of $ mcist(K_{m, n, r}\Box P_{s}) $ by constructing $ \lfloor\frac{n+r}{2}\rfloor $ completely independent spanning trees in $ K_{m, n, r}\Box P_{s} $.

We construct $ \lfloor\frac{n+r}{2}\rfloor $ completely independent spanning trees $ T_{1}, \cdots, T_{\lfloor\frac{n+r}{2}\rfloor} $ as follows:

If $ i\leq r $, then let

If $ i > r $, then let

It is easy to see that $ T_{1}, T_{2}, \cdots, T_{\lfloor\frac{n+r}{2}\rfloor} $ are edge disjoint in Figure 1. Note that every spanning tree $ T_{i} $ contains $ 3s $ internal vertices $ \{u_{i}^{l}, v_{i}^{l}, w_{i}^{l}|1\leq i \leq m, 1\leq l\leq s\} $ (or $ 4s $ internal vertices $ \{v_{i}^{l}, v_{i+1}^{l}, w_{i}^{l}, w_{i+1}^{l}| 1\leq l\leq s\} $) which are leaves in $ T_{j} (j\neq i) $. Hence, by Lemma 2, $ T_{1}, T_{2}, \cdots, T_{\lfloor\frac{n+r}{2}\rfloor} $ are completely independent spanning trees as Figure 3. Therefore, $ mcist(K_{m, n, r}\Box P_{s})\geq \lfloor\frac{n+r}{2}\rfloor $ and further it holds. □

An immediate consequence of the above theorem is the following corollary.

Corollary 3.3. Let $ m, n, r $ be integers and $ m\geq n\geq r, n+r\geq4 $. We have

4.   Conclusions

Constructing CIST is has many applications on interconnection networks such as fault-tolerant broadcasting and secure message distribution. Hasunuma ^[7] proved that it is NP-complete to find the number of completely independent spanning trees for a general graph, and Hasunuma ^[8] showed also that there are two completely independent spanning trees in the Cartesian product $ C_{m}\Box C_{n} $ for all $ m\geq 3, \ n\geq 3 $. Therefore, it is meaningful to study the existence of completely independent spanning trees for special graphs. In this paper, we cleverly use the characterization of completely independent spanning trees to determine the number of completely independent spanning trees in 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} $. It is natural and interesting to consider the following problem, that is,

Problem 4.1. How can we determine the number of completely independent spanning trees in the Cartesian product graph of any two connected graphs?

Acknowledgments

The authors thank the referees for their remarks that allowed to improve the clarity of this paper. Xia Hong is financially supported by National Natural Science Foundation of China (Grant No. 12126336) and the Young backbone teachers in Luoyang Normal College (Grant No. 2021XJGGJS-07). Wei Feng is financially supported by Natural Science Foundation of Inner Mongolia autonomous regions (Grant No. 2022LHMS01006) and the Programs Foundation of basic scientific research of colleges and universities directly under Inner Mongolia Autonomous Region in 2022 (Grant No. GXKY22156).

Conflict of interest

The authors declare that they have no conflicts of interest.