Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1710035 | Applied Mathematics Letters | 2009 | 4 Pages |
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
Xueliang Li, Zhixia Xu,