Article ID Journal Published Year Pages File Type
1710035 Applied Mathematics Letters 2009 4 Pages PDF
Abstract

Given a graph GG and a subgraph HH of GG, let rb(G,H)rb(G,H) be the minimum number rr for which any edge-coloring of GG with rr colors has a rainbow subgraph HH. The number rb(G,H)rb(G,H) is called the rainbow number of HH with respect to GG. Denote as mK2mK2 a matching of size mm and as Bn,kBn,k the set of all the kk-regular bipartite graphs with bipartition (X,Y)(X,Y) such that ∣X∣=∣Y∣=n∣X∣=∣Y∣=n and k≤nk≤n. Let k,m,nk,m,n be given positive integers, where k≥3k≥3, m≥2m≥2 and n>3(m−1)n>3(m−1). We show that for every G∈Bn,kG∈Bn,k, rb(G,mK2)=k(m−2)+2rb(G,mK2)=k(m−2)+2. We also determine the rainbow numbers of matchings in paths and cycles.

Related Topics
Physical Sciences and Engineering Engineering Computational Mechanics
Authors
, ,