Many edge-disjoint rainbow spanning trees in general graphs

arXiv1704.00048MaRDI QIDQ6285033FDOQ6285033

Authors: Paul Horn, Lauren M. Nelsen 

Publication date: 31 March 2017

Abstract: A rainbow spanning tree in an edge-colored graph is a spanning tree in which each edge is a different color. Carraher, Hartke, and Horn showed that for $n$ and $C$ large enough, if $G$ is an edge-colored copy of $K_n$ in which each color class has size at most $n/2$, then $G$ has at least $lfloorn/(Clogn)floor$ edge-disjoint rainbow spanning trees. Here we strengthen this result by showing that if $G$ is any edge-colored graph with $n$ vertices in which each color appears on at most $deltacdotlambd{a}_1/2$ edges, where $deltageqClogn$ for $n$ and $C$ sufficiently large and $lambd{a}_1$ is the second-smallest eigenvalue of the normalized Laplacian matrix of $G$, then $G$ contains at least $leftlfloorfracdeltacdotlambd{a}_{1}Clognightfloor$ edge-disjoint rainbow spanning trees.

This page was built for publication: Many edge-disjoint rainbow spanning trees in general graphs

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