-
题名几类特殊树的无矛盾连通数与最小深度
- 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
[理学—基础数学]
-
-
题名图的最小度和无矛盾连通数
被引量:1
- 2
-
-
作者
严政
赵小鹏
慈永鑫
-
机构
长江大学信息与数学学院
-
出处
《长江大学学报(自然科学版)》
2022年第2期113-118,共6页
-
基金
国家自然科学基金项目“图的参数与支撑树的研究”(11601041)
湖北省教育厅科学技术研究项目“具有特定性质的生成树的研究”(D20191303)。
-
文摘
边染色图中如果一条路径至少有一种颜色仅出现一次,则称为无矛盾路径;如果任意2个不同顶点之间都存在1条无矛盾路径,则称为无矛盾连通图。图中无矛盾连通所需要的最小颜色数称为图的无矛盾连通数。结合具有割边的图和星图的结构特点,探讨了图中关于最小度的无矛盾染色,采用构造法和删除割边法,给出了满足一些最小度、阶和边数条件的图的无矛盾连通数上界。结果表明,满足阶小于ks+2s+3k+6(s≥k≥2)的连通图G,如果最小度δ(G)≥s+2,其无矛盾连通数cfc(G)≤k;2-连通图Cn(n≥3)的t-冠(t≥2)的无矛盾连通数cfc(G)=3,t=2t,t≥3;对于阶为n最小度为δ的连通图G,如果边数大于n-m-(k+1-m)(δ+1)2+(k+1-m)δ+12+k+1,m=k+1,δ=1kδ-1,δ≥2,其无矛盾连通数cfc(G)≤k。
-
关键词
连通图
最小度
边无矛盾染色
割边
无矛盾连通数
-
Keywords
connected graph
minimum degree
edge conflict-free coloring
cut-edges
conflict-free connection number
-
分类号
O157.5
[理学—基础数学]
-
-
题名几类树的无矛盾点连通数
- 3
-
-
作者
钟咏
严政
-
机构
长江大学信息与数学学院
-
出处
《数学杂志》
2022年第4期359-366,共8页
-
基金
国家自然科学基金项目(11771058)
湖北省教育厅科学技术研究项目(D20191303)。
-
文摘
本论文研究了点着色图的无矛盾点连通数的问题,利用树的结构特征获得了特殊图类Τ_(n,k)关于无矛盾点连通数的上界和下界,Τ_(n)^(A)、T_(A)和A_(d)关于无矛盾点连通数的上界.
-
关键词
无矛盾点连通数
树
上界
下界
-
Keywords
conflict-free vertex-connection number
tree
upper bound
lower bound
-
分类号
O157.5
[理学—基础数学]
-