Geodesic
Completely Independent Spanning Trees in k-th Power of Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 801-810 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2018},
     volume = {38},
     number = {3},
     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
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
%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/

[1] T. Araki, Dirac’s condition for completely independent spanning trees, J. Graph Theory 77 (2014) 171–179. doi:10.1002/jgt.21780

[2] G. Chen and S. Shan, Homeomorphically irreducible spanning trees, J. Combin. Theory Ser. B 103 (2013) 409–414. doi:10.1016/j.jctb.2013.04.001

[3] G. Fan, Y. Hong and Q. Liu, Ore’s condition for completely independent spanning trees, Discrete Appl. Math. 177 (2014) 95–100. doi:10.1016/j.dam.2014.06.002

[4] T. Hasunuma, Completely independent spanning trees in the underlying graph of a line digraph, Discrete Math. 234 (2001) 149–157. doi:10.1016/S0012-365X(00)00377-0

[5] T. Hasunuma, Completely independent spanning trees in maximal planar graphs, in: Proceedings of the 28th Graph-Theoretic Concepts Computer Science (WG 2002), Lecture Notes in Comput. Sci. 2573 (2002) 235–245. doi:10.1007/3-540-36379-3_21

[6] X. Hong and Q. Liu, Degree condition for completely independent spanning trees, Inform. Process. Lett. 116 (2016) 644–648. doi:10.1016/j.ipl.2016.05.004

[7] C.St.J.A. Nash-Williams, Edge-disjoint spanning trees of finite graphs, J. Lond. Math. Soc. 36 (1961) 445–450. doi:10.1112/jlms/s1-36.1.445

[8] F. Péterfalvi, Two counterexamples on completely independent spanning trees, Discrete Math. 312 (2012) 808–810. doi:10.1016/j.disc.2011.11.015

[9] W.T. Tutte, On the problem of decomposing a graph into n connected factors, J. Lond. Math. Soc. 36 (1961) 221–230. doi:10.1112/jlms/s1-36.1.221