Completely Independent Spanning Trees in (Partial) k-Trees

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 -