典型文献
随机正则图k-彩虹指数的渐近结果
文献摘要：
设G是一个带有边染色的连通图,其中相邻边可以染相同颜色.G中的一棵树被称作彩虹树,如果该树中所有边都染不同颜色.给定整数k≥2,G的k-彩虹染色是一个边染色,满足对于G中的任意k元点集S,都存在一棵连接了 S中所有顶点的彩虹树.G的k-彩虹指数rxk(G)是G的k-彩虹染色所需的最少颜色数.本文主要研究了随机正则图的k-彩虹指数.我们利用边分裂引理和对某些随机图直径的估计证明了:对于固定整数k≥2和r≥2k+1,rxk(Gn,r)=O(logn)大概率成立,并且这个结果是渐近紧的.
文献关键词：
图染色;k-彩虹指数;随机正则图;直径
中图分类号：
作者姓名：
蔡庆琼;杨璐
作者机构：
南开大学计算机学院,天津,300350;天津市网络与数据安全技术重点实验室,天津,300350
文献出处：
引用格式：
[1]蔡庆琼;杨璐-.随机正则图k-彩虹指数的渐近结果)[J].数学进展,2022(06):989-995
A类：
随机正则图,rxk
B类：
彩虹,渐近,有边,边染色,连通图,邻边,一棵树,被称作,整数,点集,顶点,色数,引理,随机图,2k+1,Gn,logn,大概,图染色
AB值：
0.346738
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
