Completely independent spanning trees in some regular graphs

详细信息    查看全文

• 作者：Benoit Darties^a ; ^{benoit.darties@u-bourgogne.fr} ; Nicolas Gastineau^a ; ^b ; ^{Nicolas.Gastineau@u-bourgogne.fr} ; Olivier Togni^a ; ^{Olivier.Togni@u-bourgogne.fr}
• 关键词：Spanning tree ; Cartesian product ; Completely independent spanning tree
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P2
• 页码：163-174
• 全文大小：467 K
• 卷排序：217

文摘

Let k≥2k≥2 be an integer and T1,…,TkT1,…,Tk be spanning trees of a graph GG. If for any pair of vertices {u,v}{u,v} of V(G)V(G), the paths between uu and vv in every TiTi, 1≤i≤k1≤i≤k, do not contain common edges and common vertices, except the vertices uu and vv, then T1,…,TkT1,…,Tk are completely independent spanning trees in GG. For 2k2k-regular graphs which are 2k2k-connected, such as the Cartesian product of a complete graph of order 2k−12k−1 and a cycle, and some Cartesian products of three cycles (for k=3k=3), the maximum number of completely independent spanning trees contained in these graphs is determined and it turns out that this maximum is not always kk.