solidot新版网站常见问题,请点击这里查看。

Graphs with conflict-free connection number two. (arXiv:1707.01634v1 [math.CO])

来源于:arXiv
An edge-colored graph $G$ is \emph{conflict-free connected} if any two of its vertices are connected by a path, which contains a color used on exactly one of its edges. The \emph{conflict-free connection number} of a connected graph $G$, denoted by $cfc(G)$, is the smallest number of colors needed in order to make $G$ conflict-free connected. For a graph $G,$ let $C(G)$ be the subgraph of $G$ induced by its set of cut-edges. In this paper, we first show that for a connected noncomplete graph $G$ of order $n$ such that $C(G)$ is a linear forest, if $\delta(G)\geq 2$, then $cfc(G)=2$ for $4 \leq n\leq 8 $; if $\delta(G)\geq \max\{3, \frac{n-4}{5}\}$, then $cfc(G)=2$ for $n\geq 9$. Moreover, the minimum degree conditions are best possible. Next, we prove that for a connected noncomplete graph of order $n\geq 33$ such that $C(G)$ is a linear forest and $d(x)+d(y)\geq \frac{2n-9}{5}$ for each pair of two nonadjacent vertices $x, y$ of $V(G)$, then $cfc(G)=2$. Moreover, the degree sum condit 查看全文>>