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} $.
Citation: Xia Hong, Wei Feng. Completely independent spanning trees in some Cartesian product graphs[J]. AIMS Mathematics, 2023, 8(7): 16127-16136. doi: 10.3934/math.2023823
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} $.
| [1] |
T. Araki, Dirac's condition for completely independent spanning trees, J. Graph Theory, 77 (2014), 171–179. https://doi.org/10.1002/jgt.21780 doi: 10.1002/jgt.21780
|
| [2] |
D. Benoit, G. Nicolas, T. Olivier, Completely independent spanning trees in some regular graphs, Discrete Appl. Math., 217 (2017), 163–174. https://doi.org/10.1016/j.dam.2016.09.007 doi: 10.1016/j.dam.2016.09.007
|
| [3] |
H. Y. Chang, H. L. Wang, J. S. Yang, J. M. Chang, A note on the degree condition of completely independent spanning trees, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E98 (2015), 2191–2196. https://doi.org/10.1587/TRANSFUN.E98.A.2191 doi: 10.1587/TRANSFUN.E98.A.2191
|
| [4] |
X. D. Chen, M. C. Li, L. M. Xiong, Two completely independent spanning trees of claw-free graphs, Discrete Math., 345 (2022), 113080. https://doi.org/10.1016/j.disc.2022.113080 doi: 10.1016/j.disc.2022.113080
|
| [5] |
G. H. Fan, Y. M. Hong, Q. H. Liu, Ore's condition for completely independent spanning trees, Discrete Appl. Math., 177 (2014), 95–100. https://doi.org/10.1016/j.dam.2014.06.002 doi: 10.1016/j.dam.2014.06.002
|
| [6] |
T. Hasunuma, Completely independent spanning trees in the underlying graph of a line digraph, Discrete Math., 234 (2001), 149–157. https://doi.org/10.1016/S0012-365X(00)00377-0 doi: 10.1016/S0012-365X(00)00377-0
|
| [7] | T. Hasunuma, Completely independent spanning trees in maximal planar graphs, 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG2002), 2002,235–245. https://doi.org/10.1007/3-540-36379-3-21 |
| [8] |
T. Hasunuma, C. Morisaka, Completely independent spanning trees in torus networks, Network, 60 (2012), 59–69. https://doi.org/10.1002/net.20460 doi: 10.1002/net.20460
|
| [9] | T. Hasunuma, Minimum degree conditions and optimal graphs for completely independent spanning trees, International Workshop on Combinatorial Algorithms, 2016,260–273. https://doi.org/10.1007/978-3-319-29516-9-22 |
| [10] |
X. Hong, Q. H. Liu, Degree condition for completely independent spanning trees, Inf. Process. Lett., 116 (2016), 644–648. https://doi.org/10.1016/j.ipl.2016.05.004 doi: 10.1016/j.ipl.2016.05.004
|
| [11] |
X. Hong, Completely independent spanning trees in $k$-th power of graphs, Discuss. Math. Graph Theory, 38 (2018), 801–810. https://doi.org/10.7151/dmgt.2038 doi: 10.7151/dmgt.2038
|
| [12] | X. Hong, On completely independent spanning trees in powers of graphs, Utilitas Math., 108 (2018), 73–87. |
| [13] |
X. Hong, H. Zhang, A Hamilton sufficient condition for completely independent spanning tree, Discrete Appl. Math., 279 (2020), 183–187. https://doi.org/10.1016/j.dam.2019.08.013 doi: 10.1016/j.dam.2019.08.013
|
| [14] |
A. Itai, M. Rodeh, The multi-tree approach to reliability in distributed networks, Inf. Comput., 79 (1988), 43–59. https://doi.org/10.1016/0890-5401(88)90016-8 doi: 10.1016/0890-5401(88)90016-8
|
| [15] |
M. Matsushita, Y. Otachi, T. Araki, Completely independent spanning trees in (partial) $k$-trees, Discuss. Math. Graph Theory, 35 (2015), 427–437. https://doi.org/10.7151/dmgt.1806 doi: 10.7151/dmgt.1806
|
| [16] |
C. Nash-Williams, Edge-disjoint spanning trees of finite graphs, J. Lond. Math. Soc., 36 (1961), 445–450. https://doi.org/10.1112/jlms/s1-36.1.445 doi: 10.1112/jlms/s1-36.1.445
|
| [17] | K. J. Pai, S. M. Tang, J. M. Chang, J. S. Yang, Advances in intelligent systems and applications, Spring, 2013,107–113. https://doi.org/10.1007/978-3-642-35452-6-13 |
| [18] |
F. Péterfalvi, Two counterexamples on completely independent spanning trees, Discrete Math., 312 (2012), 808–810. https://doi.org/10.1016/j.disc.2011.11.015 doi: 10.1016/j.disc.2011.11.015
|
| [19] |
Y. F. Wang, B. L. Cheng, Y. Qian, D. J. Wang, Constructing completely independent spanning trees in a family of Line-Graph-Based data center networks, IEEE Trans. Comput., 71 (2021), 1194–1203. https://doi.org/10.1109/TC.2021.3077587 doi: 10.1109/TC.2021.3077587
|
| [20] | J. Yuan, R. Zhang, A. X. Liu, Degree conditions for completely independent spanning trees of bipartite graphs, Graphs Combinatorics, 38 (2022), 179. |
Figures(3)
Xia Hong, Wei Feng. Completely independent spanning trees in some Cartesian product graphs[J]. AIMS Mathematics, 2023, 8(7): 16127-16136. doi: 10.3934/math.2023823
DownLoad: