Geodesic
Completely Independent Spanning Trees in (Partial) k-Trees
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 3, pp. 427-437.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: completely independent spanning trees, partial k-trees 
@article{DMGT_2015_35_3_a2,
     author = {Matsushita, Masayoshi and Otachi, Yota and Araki, Toru},
     title = {Completely {Independent} {Spanning} {Trees} in {(Partial)} {k-Trees}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {427--437},
     publisher = {mathdoc},
     volume = {35},
     number = {3},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a2/}
}
TY  - JOUR
AU  - Matsushita, Masayoshi
AU  - Otachi, Yota
AU  - Araki, Toru
TI  - Completely Independent Spanning Trees in (Partial) k-Trees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 427
EP  - 437
VL  - 35
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a2/
LA  - en
ID  - DMGT_2015_35_3_a2
ER  - 
%0 Journal Article
%A Matsushita, Masayoshi
%A Otachi, Yota
%A Araki, Toru
%T Completely Independent Spanning Trees in (Partial) k-Trees
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 427-437
%V 35
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a2/
%G en
%F DMGT_2015_35_3_a2
Matsushita, Masayoshi; Otachi, Yota; Araki, Toru. Completely Independent Spanning Trees in (Partial) k-Trees. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 3, pp. 427-437. http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a2/

[1] T. Araki, Dirac’s condition for completely independent spanning trees, J. Graph Theory 77 (2014) 171-179. doi:10.1002/jgt.21780

[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

[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

[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

[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

[6] B. Courcelle, The monadic second-order logic of graphs III: tree-decompositions, minors and complexity issues, Theor. Inform. Appl. 26 (1992) 257-286.

[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

[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

[9] T. Hasunuma and C. Morisaka, Completely independent spanning trees in torus networks, Networks 60 (2012) 59-69. doi:10.1002/net.20460

[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

[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