-
题名几类特殊树的无矛盾连通数与最小深度
- 1
-
-
作者
严政
邓语馨
慈永鑫
-
机构
长江大学信息与数学学院
-
出处
《长江大学学报（自然科学版）》
2024年第2期110-114,共5页
-
基金
国家自然科学基金项目“三层规划问题的算法设计与应用研究”(11771058)
湖北省教育厅科学技术研究项目“具有特定性质的生成树的研究”(D20191303)。
-
文摘
在一个边着色图G中,如果一条路径上有一种颜色只出现一次,则称这条路为无矛盾的。如果图G的任意两点间都存在一条路径是无矛盾连通的,则称图G为无矛盾连通图。图的无矛盾连通数cfc(G)是指使G为无矛盾连通图所需的最小颜色数。树的深度是研究树的无矛盾连通数行之有效的研究方法。研究了几类特殊树的无矛盾连通数与最小深度,刻画了最小深度与无矛盾连通数相等的树。首先,证明了如果n阶树T满足Δ(T)≥n/2,则cfc(T)=D(T)=Δ(T);其次,研究几类特殊树的最小深度与无矛盾连通数并给出了它们的界;最后,在树的最大度和阶已知的情形下,利用最小深度与阶的关系给出最小深度与无矛盾连通数的值。
-
关键词
连通图
最小深度
边无矛盾染色
无矛盾连通数
-
Keywords
conflict-free connected graph
minimum depth
conflict-free edge coloring
conflict-free connection number
-
分类号
O157.5
[理学—数学]
-
