solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看545次
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 查看全文>>