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

Masayoshi Matsushita; Yota Otachi; Toru Araki

Discussiones Mathematicae Graph Theory (2015)

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

## Access Full Article

top## Abstract

top## How to cite

topMasayoshi 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] 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] 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] 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] 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] 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. Zbl0754.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] Zbl0984.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] Zbl1251.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] Zbl1238.05060

## NotesEmbed ?

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