A path in an(a) edge(vertex)-colored graph is called emph{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 emph{conflict-free (vertex-)connected} if there is a conflict-free path between each pair of distinct vertices. We call the graph $G$ emph{strongly conflict-free connected }if there exists a conflict-free path of length $d_G(u,v)$ for every two vertices $u,vin V(G)$. And the emph{strong conflict-free connection number} of a connected graph $G$, denoted by $scfc(G)$, is defined as the smallest number of colors that are required to make $G$ strongly conflict-free connected. In this paper, we first investigate the question: Given a connected graph $G$ and a coloring $c: E(or V)rightarrow {1,2,cdots,k} (kgeq 1)$ of the graph, determine whether or not $G$ is, respectively, conflict-free connected, vertex-conflict-free connected, strongly conflict-free connected under coloring $c$. We solve this question by providing polynomial-time algorithms. We then show that it is NP-complete to decide whether there is a k-edge-coloring $(kgeq 2)$ of $G$ such that all pairs $(u,v)in P (Psubset Vtimes V)$ are strongly conflict-free connected. Finally, we prove that the problem of deciding whether $scfc(G)leq k$ $(kgeq 2)$ for a given graph $G$ is NP-complete.
تحميل البحث