2017/05/15 by Bo Deng, Deng, Bo, Wen J. Li +7 · 1 citation
Computer Science · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1705.05317
A path in an edge-colored graph is called conflict-free if it contains at least one color used on exactly one of its edges. An edge-colored graph G is conflict-free connected if for any two distinct vertices of G, there is a conflict-free path connecting them. For a connected graph G, the conflict-free connection number of G, denoted by cfc(G), is defined as the minimum number of colors that are required to make G conflict-free connected. In this paper, we investigate the conflict-free connection numbers of connected claw-free graphs, especially line graphs. We first show that for an arbitrary connected graph G, there exists a positive integer k such that cfc(Lk(G))≤ 2. Secondly, we get the exact value of the conflict-free connection number of a connected claw-free graph, especially a connected line graph. Thirdly, we prove that for an arbitrary connected graph G and an arbitrary positive integer k, we always have cfc(Lk+1(G))≤ cfc(Lk(G)), with only the exception that G is isomorphic to a star of order at least~5 and k=1. Finally, we obtain the exact values of cfc(Lk(G)), and use them as an efficient tool to get the smallest nonnegative integer k0 such that cfc(Lk0(G))=2.