文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Rainbow number of matchings in regular bipartite graphs
侵权投诉

Rainbow number of matchings in regular bipartite graphs

Given a graph $G$ and a subgraph $H$ of $G$, let $rb(G,H)$ be the minimum number $r$ for which any edge-coloring of $G$ with $r$ colors has a rainbow subgraph $H$. The number $rb(G,H)$ is called the rainbow number of $H$ with respect to $G$. Denote $mK_2$

7

2

v

o

N

9

1

]

OC

.

h

ta

m

[

1

v

6

4

8

2

.

1

1

7

:0v

i

X

r

aRainbownumberofmatchingsinregularbipartitegraphs XueliangLi1andZhixiaXu1,21CenterforCombinatoricsandLPMC-TJKLCNankaiUniversity,Tianjin300071,China.Email:lxl@nankai.edu.cn2CollegeofMathematicsandSystemSciences,XinjiangUniversityUrumuqi,830046,China.Email:irisxuzx@gmail.comAbstractGivenagraphGandasubgraphHofG,letrb(G,H)bethemin-imumnumberrforwhichanyedge-coloringofGwithrcolorshasarainbowsubgraphH.Thenumberrb(G,H)iscalledtherainbownumberofHwithrespecttoG.DenotemK2amatchingofsizemandBn,kak-regularbipartitegraphwithbipartition(X,Y)suchthat|X|=|Y|=nandk≤n.Inthispaperwegiveanupperandlowerboundforrb(Bn,k,mK2),andshowthatforgivenkandm,ifnislargeenough,rb(Bn,k,mK2)canreachthelowerbound.Wealsodeterminetherainbownumberofmatchingsinpathsandcycles.Keywords:edge-coloredgraph,rainbowsubgraph,rainbownumber,matching,regularbipartitegraph

AMSSubjectClassi cation2000:05C15,05C35,05C55,05C70.1Introduction

WeuseBondyandMurty[3]forterminologyandnotationsnotde nedhereandconsidersimple, nitegraphsonly.

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email