# Completely Independent Spanning Trees in (Partial) k-Trees

• Volume: 35, Issue: 3, page 427-437
• ISSN: 2083-5892

top

## Abstract

top
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.

## How to cite

top

Masayoshi Matsushita, Yota Otachi, and Toru Araki. "Completely Independent Spanning Trees in (Partial) k-Trees." Discussiones Mathematicae Graph Theory 35.3 (2015): 427-437. <http://eudml.org/doc/271215>.

@article{MasayoshiMatsushita2015,
abstract = {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.},
author = {Masayoshi Matsushita, Yota Otachi, Toru Araki},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {completely independent spanning trees; partial k-trees.; partial -trees},
language = {eng},
number = {3},
pages = {427-437},
title = {Completely Independent Spanning Trees in (Partial) k-Trees},
url = {http://eudml.org/doc/271215},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Masayoshi Matsushita
AU - Yota Otachi
AU - Toru Araki
TI - Completely Independent Spanning Trees in (Partial) k-Trees
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 3
SP - 427
EP - 437
AB - 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.
LA - eng
KW - completely independent spanning trees; partial k-trees.; partial -trees
UR - http://eudml.org/doc/271215
ER -

## References

top
1. [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] Zbl1303.05133
2. [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] Zbl0666.68067
3. [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] Zbl0912.68148
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[WoS][Crossref] Zbl1253.68163
5. [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. [6] B. Courcelle, The monadic second-order logic of graphs III: tree-decompositions, minors and complexity issues, Theor. Inform. Appl. 26 (1992) 257-286. Zbl0754.03006
7. [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] Zbl0984.05022
8. [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. [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] Zbl1251.68034
10. [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. [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] Zbl1238.05060

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.