6533b857fe1ef96bd12b5003
RESEARCH PRODUCT
Completely independent spanning trees in some regular graphs
Nicolas GastineauBenoit DartiesOlivier Tognisubject
FOS: Computer and information sciences[ MATH ] Mathematics [math]Discrete Mathematics (cs.DM)Small Depths0102 computer and information sciences02 engineering and technology[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]01 natural sciencesCombinatoricssymbols.namesakeCompletely independent spanning treeFOS: Mathematics0202 electrical engineering electronic engineering information engineeringCartesian productDiscrete Mathematics and CombinatoricsMathematics - Combinatorics[MATH]Mathematics [math]MathematicsConstructionSpanning treeSpanning treeApplied MathematicsComplete graph020206 networking & telecommunications[ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM]Cartesian productIndependent spanning treesGraphPlanar graphPlanar Graphs010201 computation theory & mathematicssymbolsCompletely independent spanning tree.Combinatorics (math.CO)Computer Science - Discrete Mathematicsdescription
International audience; Let k >= 2 be an integer and T-1,..., T-k be spanning trees of a graph G. If for any pair of vertices {u, v} of V(G), the paths between u and v in every T-i, 1 <= i <= k, do not contain common edges and common vertices, except the vertices u and v, then T1,... Tk are completely independent spanning trees in G. For 2k-regular graphs which are 2k-connected, such as the Cartesian product of a complete graph of order 2k-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. (C) 2016 Elsevier B.V. All rights reserved.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2014-06-11 |