AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
PDF (479.9 KB)
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Research Article | Open Access

Completely independent spanning trees in some Cartesian product graphs

Xia Hong1( )Wei Feng2
Department of mathematics, Luoyang Normal University, Luoyang 471022, China
College of mathematics and Physics, Inner Mongolia Minzu University, Tongliao 028000, China
Show Author Information

Abstract

Let T 1 , T 2 , , T k 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 T 1 , T 2 , , T k are completely independent. Hasunuma showed that there are two completely independent spanning trees in any 4-connected maximal planar graph, and that given a graph G, the problem of deciding whether there exist two completely independent spanning trees in G is NP-complete. In this paper, we consider the number of completely independent spanning trees in some Cartesian product graphs such as W m P n , W m C n , K m , n P r , K m , n C r , K m , n , r P s , K m , n , r C s .

CLC number: 05C05

References

【1】
【1】
 
 
AIMS Mathematics
Pages 16127-16136

{{item.num}}

Comments on this article

Go to comment

< Back to all reports

Review Status: {{reviewData.commendedNum}} Commended , {{reviewData.revisionRequiredNum}} Revision Required , {{reviewData.notCommendedNum}} Not Commended Under Peer Review

Review Comment

Close
Close
Cite this article:
Hong X, Feng W. Completely independent spanning trees in some Cartesian product graphs. AIMS Mathematics, 2023, 8(7): 16127-16136. https://doi.org/10.3934/math.2023823

3

Views

0

Downloads

0

Crossref

0

Web of Science

0

Scopus

Received: 12 February 2023
Revised: 20 April 2023
Accepted: 24 April 2023
Published: 15 July 2023
©2023 the Author(s), licensee AIMS Press.

This is an open access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0)