Completely independent spanning trees in some regular graphs

DOI10.1016/J.DAM.2016.09.007zbMATH Open1358.05053arXiv1409.6002OpenAlexW2962923546MaRDI QIDQ516807FDOQ516807

Authors: B. Darties, Nicolas Gastineau, Olivier Togni

Publication date: 15 March 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Let

k g e 2

be an integer and

T_{1}, l d o t s, T_{k}

be spanning trees of a graph

G

. If for any pair of vertices

(u, v)

of

V (G)

, the paths from

u

to

v

in each

T_{i}

,

1 l e i l e k

, do not contain common edges and common vertices, except the vertices

u

and

v

, then

T_{1}, l d o t s, T_{k}

are completely independent spanning trees in

G

. For

2 k

-regular graphs which are

2 k

-connected, such as the Cartesian product of a complete graph of order

2 k - 1

and a cycle and some Cartesian products of three cycles (for

k = 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

k

.

Full work available at URL: https://arxiv.org/abs/1409.6002

Recommendations

zbMATH Keywords

Cartesian product spanning tree completely independent spanning tree

Mathematics Subject Classification ID

Trees (05C05) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

Cited In (28)

This page was built for publication: Completely independent spanning trees in some regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q516807)