Two spanning trees T1 and T2 of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T1 and T2 are internally disjoint. For a graph G, we denote the maximum number of pairwise completely independent spanning trees by cist(G). In this paper, we consider cist(G) when G is a partial k-tree. First we show that [k/2] ≤ cist(G) ≤ k − 1 for any k-tree G. Then we show that for any p ∈ {[k/2], . . . , k − 1}, there exist infinitely many k-trees G such that cist(G) = p. Finally we consider algorithmic aspects for computing cist(G). Using Courcelle’s theorem, we show that there is a linear-time algorithm that computes cist(G) for a partial k-tree, where k is a fixed constant.
@article{bwmeta1.element.doi-10_7151_dmgt_1806,
author = {Masayoshi Matsushita and Yota Otachi and Toru Araki},
title = {Completely Independent Spanning Trees in (Partial) k-Trees},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {427-437},
zbl = {1317.05029},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1806}
}
Masayoshi Matsushita; Yota Otachi; Toru Araki. Completely Independent Spanning Trees in (Partial) k-Trees. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 427-437. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1806/
[1] T. Araki, Dirac’s condition for completely independent spanning trees, J. Graph Theory 77 (2014) 171-179. doi:10.1002/jgt.21780[WoS][Crossref] | Zbl 1303.05133
[2] S. Arnborg and A. Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Appl. Math. 23 (1989) 11-24. doi:10.1016/0166-218X(89)90031-0[Crossref] | Zbl 0666.68067
[3] H.L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci. 209 (1998) 1-45. doi:10.1016/S0304-3975(97)00228-4[Crossref] | Zbl 0912.68148
[4] H.L. Bodlaender, F.V. Fomin, P.A. Golovach, Y. Otachi and E.J. van Leeuwen, Parameterized complexity of the spanning tree congestion problem, Algorithmica 64 (2012) 85-111. doi:10.1007/s00453-011-9565-7[WoS][Crossref] | Zbl 1253.68163
[5] H.L. Bodlaender and A.M.C.A. Koster, Combinatorial optimization on graphs of bounded treewidth, Comput. J. 51 (2008) 255-269. doi:10.1093/comjnl/bxm037 [WoS][Crossref]
[6] B. Courcelle, The monadic second-order logic of graphs III: tree-decompositions, minors and complexity issues, Theor. Inform. Appl. 26 (1992) 257-286. | Zbl 0754.03006
[7] T. Hasunuma, Completely independent spanning trees in the underlying graph of a line digraph, Discrete Math. 234 (2001) 149-157. doi:10.1016/S0012-365X(00)00377-0[Crossref] | Zbl 0984.05022
[8] T. Hasunuma, Completely independent spanning trees in maximal planar graphs in: Proceedings of 28th Graph Theoretic Concepts of Computer Science (WG 2002), LNCS 2573, Springer-Verlag Berlin (2002) 235-245. doi:10.1007/3-540-36379-3 21[Crossref]
[9] T. Hasunuma and C. Morisaka, Completely independent spanning trees in torus networks, Networks 60 (2012) 59-69. doi:10.1002/net.20460[WoS][Crossref] | Zbl 1251.68034
[10] P. Hlinĕný, S. Oum, D. Seese and G. Gottlob, Width parameters beyond tree-width and their applications, Comput. J. 51 (2008) 326-362. doi:10.1093/comjnl/bxm052[WoS][Crossref]
[11] F. Péterfalvi, Two counterexamples on completely independent spanning trees, Dis- crete Math. 312 (2012) 808-810. doi:10.1016/j.disc.2011.11.0 [WoS][Crossref] | Zbl 1238.05060