Completely independent spanning trees in some regular graphs

From MaRDI portal

Jump to:navigation, search

DOI10.1016/J.DAM.2016.09.007MaRDI QIDQ516807zbMATH OpenOpenAlexFDO

Authors B. Darties, Nicolas Gastineau, Olivier Togni

Publication date 15 March 2017

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

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

zbMATH Keywords

Cartesian product spanning tree completely independent spanning tree

Mathematics Subject Classification ID

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

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

.

Recommendations

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)

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Completely_independent_spanning_trees_in_some_regular_graphs&oldid=62525625"