Title of article :
The rainbow number of matchings in regular bipartite graphs
Author/Authors :
Li، نويسنده , , Xueliang and Xu، نويسنده , , Zhixia، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
Pages :
4
From page :
1525
To page :
1528
Abstract :
Given a graph G and a subgraph H of G , let r b ( G , H ) be the minimum number r for which any edge-coloring of G with r colors has a rainbow subgraph H . The number r b ( G , H ) is called the rainbow number of H with respect to G . Denote as m K 2 a matching of size m and as B n , k the set of all the k -regular bipartite graphs with bipartition ( X , Y ) such that ∣ X ∣ = ∣ Y ∣ = n and k ≤ n . Let k , m , n be given positive integers, where k ≥ 3 , m ≥ 2 and n > 3 ( m − 1 ) . We show that for every G ∈ B n , k , r b ( G , m K 2 ) = k ( m − 2 ) + 2 . We also determine the rainbow numbers of matchings in paths and cycles.
Keywords :
Edge-colored graph , Rainbow subgraph , Matching , Regular bipartite graph , rainbow number
Journal title :
Applied Mathematics Letters
Serial Year :
2009
Journal title :
Applied Mathematics Letters
Record number :
1526284
Link To Document :
بازگشت