Wszystkie pola: completely independent spanning trees - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Completely Independent Spanning Trees in k-th Power of Graphs
Autorzy:: Hong, Xia
Powiązania:: https://bibliotekanauki.pl/articles/31342277.pdf
Data publikacji:: 2018-08-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: completely independent spanning tree
power of graphs
spanning trees
Opis:: Let T₁, T₂, . . ., T_k be spanning trees of a graph G. For any two vertices u, v of G, if the paths from u to v in these k trees are pairwise openly disjoint, then we say that T₁, T₂, . . ., T_k are completely independent. Araki showed that the square of a 2-connected graph G on n vertices with n ≥ 4 has two completely independent spanning trees. In this paper, we prove that the k-th power of a k-connected graph G on n vertices with n ≥ 2k has k completely independent spanning trees. In fact, we prove a stronger result: if G is a connected graph on n vertices with δ(G) ≥ k and n ≥ 2k, then the k-th power G^k of G has k completely independent spanning trees.
Źródło:: Discussiones Mathematicae Graph Theory; 2018, 38, 3; 801-810
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

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 T₁ and T₂ of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T₁ and T₂ 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ł

Informacja