- Tytuł:
- Completely Independent Spanning Trees in (Partial) k-Trees
- Autorzy:
-
Matsushita, Masayoshi
Otachi, Yota
Araki, Toru - Powiązania:
- https://bibliotekanauki.pl/articles/31339419.pdf
- Data publikacji:
- 2015-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
completely independent spanning trees
partial k-trees - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2015, 35, 3; 427-437
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł