2019/02/28 by Xueliang Li, Li, Xueliang, Xiaoyu Zhu +1 · 1 citation
Computer Science · #05C05 #05C15 #05C40 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1902.10881
openalex publication_date 2019/02/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A path in an(a) edge(vertex)-colored graph is called a conflict-free path if there exists a color used on only one of its edges(vertices). An(A) edge(vertex)-colored graph is called conflict-free (vertex-)connected if for each pair of distinct vertices, there is a conflict-free path connecting them. For a connected graph G, the conflict-free (vertex-)connection number of G, denoted by cfc(G)(or~vcfc(G)), is defined as the smallest number of colors that are required to make G conflict-free (vertex-)connected. In this paper, we first give the exact value cfc(T) for any tree T with diameters 2,3 and 4. Based on this result, the conflict-free connection number is determined for any graph G with diam(G)≤ 4 except for those graphs G with diameter 4 and h(G)=2. In this case, we give some graphs with conflict-free connection number 2 and 3, respectively. For the conflict-free vertex-connection number, the exact value vcfc(G) is determined for any graph G with diam(G)≤ 4.