2017/05/23 by Hong Chang, Chang, Hong, Zhong Huang +7
Computer Science · Mathematics · #05C15 #05C40 #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems #math.CO #msc:05C15 #msc:05C40 #msc:05C75
paper · pdf · doi:10.48550/arxiv.1705.08316
25 pages
arxiv created 2017/05/23 · openalex publication_date 2017/05/23 · arxiv updated 2017/05/24 · openalex created_date 2017/06/05 · openalex updated_date 2026/07/28
An edge-colored graph G is conflict-free connected if, between each pair of distinct vertices, there exists a path containing a color used on exactly one of its edges. The conflict-free connection number of a connected graph G, denoted by cfc(G), is defined as the smallest number of colors that are needed in order to make G conflict-free connected. In this paper, we determine all trees T of order n for which cfc(T)=n-t, where t≥ 1 and n≥ 2t+2 . Then we prove that 1≤ cfc(G)≤ n-1 for a connected graph G, and characterize the graphs G with cfc(G)=1,n-4,n-3,n-2,n-1, respectively. Finally, we get the Nordhaus-Gaddum-type theorem for the conflict-free connection number of graphs, and prove that if G and G are connected, then 4≤ cfc(G)+cfc(G)≤ n and 4≤ cfc(G)⋅ cfc(G)≤2(n-2), and moreover, cfc(G)+cfc(G)=n or cfc(G)⋅ cfc(G)=2(n-2) if and only if one of G and G is a tree with maximum degree n-2 or a P5, and the lower bounds are sharp.