Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: completely independent spanning trees

Sortuj według:

Ogranicz wyniki do:

Completely Independent Spanning Trees in (Partial) k-Trees

100%

Matsushita M., Otachi Y., Araki T.

Discussiones Mathematicae Graph Theory

2015

tom 35

nr 3

427-437

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Araki T.

1 Matsushita M.

1 Otachi Y.

1 2015

Wyniki wyszukiwania

Completely Independent Spanning Trees in (Partial) k-Trees