图的彩虹连通数与最小度和

• 作者: 李学良 董九英
• 来源期刊: 中国科学（数学）
• 关键词: 彩虹着色 彩虹(点)连通数 控制集 参数σk(G)
• 年，卷（期）: 2013,（1）
• 所属期刊栏目: 论文
• 页码范围: 7-14
• 页数: 8页
• 语种: 中文
• DOI: 10.1360/012012-120

摘要

令G是一个阶为n且最小度为δ的连通图.当δ很小而n很大时,现有的依据于最小度参数的彩虹边连通数和彩虹点连通数的上界都很大,它们是n的线性函数.本文中,我们用另一种参数,即k个独立点的最小度和σk来代替δ,从而在很大程度上改进了彩虹边连通数和彩虹点连通数的上界.本文证明了如果G有k个独立点,那么rc(G)≤3km/σk+k+6k-3.同时也证明了下面的结果,如果σk≤7k或σk≥8k,那么rvc(G)≤(4k+2k2)/σk+k+5k;如果7k＜σk＜8k,那么rvc(G)≤(38k/9+2k2)n/σk+k+5k.文中也给出了例子说明我们的界比现有的界更好,即我们的界为rc(G)≤9k-3和rvc(G)≤9k+2k2或rvc(G)≤83k/9+ 2k2,这意味着当δ很小而σk很大时,我们的界是一个常数,而现有的界却是n的线性函数.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李学良		19	89	5.0	9.0
2	董九英		1	0	0.0	0.0