Minimum degree and conflict-free connection number of graphs
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(]),ihen 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.
conflict-free connected graphminimum depthconflict-free edge coloringconflict-free connection number
万方数据
维普
