- 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 T1, T2, . . ., Tk 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 T1, T2, . . ., Tk 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 Gk 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ł