Completely Independent Spanning Trees in k-Th Power of Graphs
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 ≥...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2018-08-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2038 |
| _version_ | 1797704427628396544 |
|---|---|
| author | Hong Xia |
| author_facet | Hong Xia |
| author_sort | Hong Xia |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T05:20:16Z |
| format | Article |
| id | doaj.art-e867de21df034af594ee5475f6a01cc5 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T05:20:16Z |
| publishDate | 2018-08-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-e867de21df034af594ee5475f6a01cc52023-09-03T07:47:23ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922018-08-0138380181010.7151/dmgt.2038dmgt.2038Completely Independent Spanning Trees in k-Th Power of GraphsHong Xia0Department of mathematics, Luoyang Normal University, Luoyang, 471022, ChinaLet 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.https://doi.org/10.7151/dmgt.2038completely independent spanning treepower of graphsspanning trees05c05 |
| spellingShingle | Hong Xia Completely Independent Spanning Trees in k-Th Power of Graphs Discussiones Mathematicae Graph Theory completely independent spanning tree power of graphs spanning trees 05c05 |
| title | Completely Independent Spanning Trees in k-Th Power of Graphs |
| title_full | Completely Independent Spanning Trees in k-Th Power of Graphs |
| title_fullStr | Completely Independent Spanning Trees in k-Th Power of Graphs |
| title_full_unstemmed | Completely Independent Spanning Trees in k-Th Power of Graphs |
| title_short | Completely Independent Spanning Trees in k-Th Power of Graphs |
| title_sort | completely independent spanning trees in k th power of graphs |
| topic | completely independent spanning tree power of graphs spanning trees 05c05 |
| url | https://doi.org/10.7151/dmgt.2038 |
| work_keys_str_mv | AT hongxia completelyindependentspanningtreesinkthpowerofgraphs |