Geodesic
Completely Independent Spanning Trees in k-th Power of Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 801-810

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: completely independent spanning tree, power of graphs, spanning trees 
@article{DMGT_2018_38_3_a10,
     author = {Hong, Xia},
     title = {Completely {Independent} {Spanning} {Trees} in k-th {Power} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {801--810},
     publisher = {mathdoc},
     volume = {38},
     number = {3},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a10/}
}
TY  - JOUR
AU  - Hong, Xia
TI  - Completely Independent Spanning Trees in k-th Power of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 801
EP  - 810
VL  - 38
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a10/
LA  - en
ID  - DMGT_2018_38_3_a10
ER  - 
%0 Journal Article
%A Hong, Xia
%T Completely Independent Spanning Trees in k-th Power of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 801-810
%V 38
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a10/
%G en
%F DMGT_2018_38_3_a10
Hong, Xia. Completely Independent Spanning Trees in k-th Power of Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 801-810. http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a10/