几类特殊树的无矛盾连通数与最小深度

Minimum degree and conflict-free connection number of graphs

在一个边着色图G中,如果一条路径上有一种颜色只出现一次,则称这条路为无矛盾的。如果图G的任意两点间都存在一条路径是无矛盾连通的,则称图G为无矛盾连通图。图的无矛盾连通数cfc(G)是指使G为无矛盾连通图所需的最小颜色数。树的深度是研究树的无矛盾连通数行之有效的研究方法。研究了几类特殊树的无矛盾连通数与最小深度,刻画了最小深度与无矛盾连通数相等的树。首先,证明了如果n阶树T满足Δ(T)≥n/2,则cfc(T)=D(T)=Δ(T);其次,研究几类特殊树的最小深度与无矛盾连通数并给出了它们的界;最后,在树的最大度和阶已知的情形下,利用最小深度与阶的关系给出最小深度与无矛盾连通数的值。

An edge-colored graph G is called conflict-free connected if each pair of distinct vertices is connected by a path which contains at least one color used on exactly one of its edges.This path is called a conflict-free path,and this coloring is called a conflict-free connection coloring of G.The conflict-free connection number of a connected graph G,denoted by cfc(G),is the smallest number of colors required to color the edges of G so that G is conflict-free connected.It is easy to obtain the conflict-free connection number of trees by studying the minimum depth of trees.In this paper,we first study the conflict-free connection number and the minimum depth of several special trees,respectively,then we give some trees satisfying the minimum depth and the conflict-free connection number are equal.We prove that if a tree T of order n satisfiesΔ(T)≥n/2,then cfc(T)=D(T)=Δ(T).Secondly,we study the minimum depth and conflict-free connection number of several special trees and obtain their bounds,respectively.when the maximum degree and order of the tree is given,we obtain the exact value of the minimum depth and the conflict-free connection number according to the relationship between the minimum depth and the order.