标题: | On the number of rainbow spanning trees in edge-colored complete graphs |
作者: | Fu, Hung-Lin Lo, Yuan-Hsun Perry, K. E. Rodger, C. A. 应用数学系 Department of Applied Mathematics |
关键字: | Edge-coloring;Complete graph;Rainbow spanning tree |
公开日期: | 1-八月-2018 |
摘要: | A spanning tree of a properly edge-colored complete graph, K, is rainbow provided that each of its edges receives a distinct color. In 1996, Brualdi and Hollingsworth conjectured that if K-2m is properly (2m 1)-edge-colored, then the edges of K-2m,, can be partitioned into m rainbow spanning trees except when m = 2. By means of an explicit, constructive approach, in this paper we construct [root 6m+9/3] mutually edge-disjoint rainbow spanning trees for any positive value of m. Not only are the rainbow trees produced, but also some structure of each rainbow spanning tree is determined in the process. This improves upon best constructive result to date in the literature which produces exactly three rainbow trees. (C) 2018 Elsevier B.V. All rights reserved. |
URI: | http://dx.doi.org/10.1016/j.disc.2018.05.008 http://hdl.handle.net/11536/145260 |
ISSN: | 0012-365X |
DOI: | 10.1016/j.disc.2018.05.008 |
期刊: | DISCRETE MATHEMATICS |
Volume: | 341 |
起始页: | 2343 |
结束页: | 2352 |
显示于类别: | Articles |