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/