Skip to main content
Article
Rainbow K-Connection in Dense Graphs
Journal of Combinatorial Mathematics and Combinatorial Computing
  • Shinya Fujita, Maebashi Institute of Technology
  • Henry Liu, Universidade Nova de Lisboa Quinta da Torre
  • Colton Magnant, Georgia Southern University
Document Type
Article
Publication Date
5-1-2015
Disciplines
Abstract

An edge-colouring of a graph G is rainbow k-connected if, for any two vertices of G, there are k internally vertex-disjoint paths joining them, each of which is rainbow (i.e., all edges of each path have distinct colours). The minimum number of colours for which there exists a rainbow k-connected colouring for G is the rainbow k-connection number of G, and is denoted by rck(G). The function rck(G) was introduced by Chartrand et al. in 2008, and has since attracted considerable interest. In this note, we shall consider the function rck(G) for complete bipartite and multipartite graphs, highly connected graphs, and random graphs.

Citation Information
Shinya Fujita, Henry Liu and Colton Magnant. "Rainbow K-Connection in Dense Graphs" Journal of Combinatorial Mathematics and Combinatorial Computing Vol. 93 (2015) p. 33 - 52 ISSN: 0835-3026
Available at: http://works.bepress.com/colton_magnant/53/