On the number of rainbow spanning trees in edge-colored complete graphs

Hung-Lin Fu; Yuan Hsun Lo; K. E. Perry; C. A. Rodger

doi:10.1016/j.disc.2018.05.008

On the number of rainbow spanning trees in edge-colored complete graphs

Hung-Lin Fu, Yuan Hsun Lo, K. E. Perry^*, C. A. Rodger

^*此作品的通信作者

應用數學系

研究成果: Article › 同行評審

6 引文斯高帕斯（Scopus）

摘要

A spanning tree of a properly edge-colored complete graph, K_n, 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 ⌊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.

原文	English
頁（從 - 到）	2343-2352
頁數	10
期刊	Discrete Mathematics
卷	341
發行號	8
DOIs	https://doi.org/10.1016/j.disc.2018.05.008
出版狀態	Published - 1 8月 2018

存取文件

10.1016/j.disc.2018.05.008

其它文件與鏈接

Link to publication in Scopus

引用此

@article{7d0fc51dfb8a46a2b9d78c481e30e220,

title = "On the number of rainbow spanning trees in edge-colored complete graphs",

abstract = "A spanning tree of a properly edge-colored complete graph, Kn, is rainbow provided that each of its edges receives a distinct color. In 1996, Brualdi and Hollingsworth conjectured that if K2m is properly (2m−1)-edge-colored, then the edges of K2m can be partitioned into m rainbow spanning trees except when m=2. By means of an explicit, constructive approach, in this paper we construct ⌊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.",

keywords = "Complete graph, Edge-coloring, Rainbow spanning tree",

author = "Hung-Lin Fu and Lo, {Yuan Hsun} and Perry, {K. E.} and Rodger, {C. A.}",

year = "2018",

month = aug,

day = "1",

doi = "10.1016/j.disc.2018.05.008",

language = "English",

volume = "341",

pages = "2343--2352",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "8",

}

TY - JOUR

T1 - On the number of rainbow spanning trees in edge-colored complete graphs

AU - Fu, Hung-Lin

AU - Lo, Yuan Hsun

AU - Perry, K. E.

AU - Rodger, C. A.

PY - 2018/8/1

Y1 - 2018/8/1

N2 - A spanning tree of a properly edge-colored complete graph, Kn, is rainbow provided that each of its edges receives a distinct color. In 1996, Brualdi and Hollingsworth conjectured that if K2m is properly (2m−1)-edge-colored, then the edges of K2m can be partitioned into m rainbow spanning trees except when m=2. By means of an explicit, constructive approach, in this paper we construct ⌊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.

AB - A spanning tree of a properly edge-colored complete graph, Kn, is rainbow provided that each of its edges receives a distinct color. In 1996, Brualdi and Hollingsworth conjectured that if K2m is properly (2m−1)-edge-colored, then the edges of K2m can be partitioned into m rainbow spanning trees except when m=2. By means of an explicit, constructive approach, in this paper we construct ⌊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.

KW - Complete graph

KW - Edge-coloring

KW - Rainbow spanning tree

UR - http://www.scopus.com/inward/record.url?scp=85047643679&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2018.05.008

DO - 10.1016/j.disc.2018.05.008

M3 - Article

AN - SCOPUS:85047643679

SN - 0012-365X

VL - 341

SP - 2343

EP - 2352

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 8

ER -

On the number of rainbow spanning trees in edge-colored complete graphs

摘要

存取文件

其它文件與鏈接

指紋

引用此