Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648714 | Discrete Mathematics | 2010 | 8 Pages |
Abstract
A kk-rainbow path in a graph with colored edges is a path of length kk where each edge has a different color. In this note, we settle the problem of obtaining a constructive kk-coloring of the edges of KnKn in which one may find, between any pair of vertices, a large number of internally disjoint kk-rainbow paths. In fact, our construction obtains the largest possible number of paths. This problem was considered in a less general setting by Chartrand et al. (2007) [6].
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Domingos Dellamonica Jr., Colton Magnant, Daniel M. Martin,