1. bookVolume 38 (2018): Issue 3 (August 2018)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Completely Independent Spanning Trees in k-Th Power of Graphs

Published Online: 19 Jun 2018
Volume & Issue: Volume 38 (2018) - Issue 3 (August 2018)
Page range: 801 - 810
Received: 28 Apr 2016
Accepted: 07 Feb 2017
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

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

MSC 2010

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

[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.00110.1016/j.jctb.2013.04.001Search in Google Scholar

[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.00210.1016/j.dam.2014.06.002Search in Google Scholar

[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-010.1016/S0012-365X(00)00377-0Search in Google Scholar

[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_2110.1007/3-540-36379-3_21Search in Google Scholar

[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.00410.1016/j.ipl.2016.05.004Search in Google Scholar

[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.44510.1112/jlms/s1-36.1.445Search in Google Scholar

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

[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.22110.1112/jlms/s1-36.1.221Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo