Strong conflict-free connection of graphs

摘要

A path P in an edge-colored graph is called a conflict-free path if there exists a color used on only one of the edges of P. An edge-colored graph G is called conflict-free connected if for each pair of distinct vertices of G there is a conflict-free path in G connecting them. The graph G is called strongly conflict-free connected if for every pair of vertices u and v of G there exists a conflict-free path of length dG(u, v) in G connecting them. For a connected graph G, the strong conflict-free connection number of G, denoted by scfc(G), is defined as the smallest number of colors that are required in order to make G strongly conflict-free connected. In this paper, we first show that if Gt is a connected graph with m ( ≥ 2) edges and t edge-disjoint triangles, then scfc(Gt)≤m−2t, and the equality holds if and only if Gt≅Sm−t,t. Then we characterize the graphs G with scfc(G)=k for k∈{1,m−3,m−2,m−1,m}. In the end, we present a complete characterization for the cubic graphs G with scfc(G)=2.