Nordhaus-Gaddum-type theorem for conflict-free connection number of graphs

arXiv1705.08316MaRDI QIDQ6287029FDOQ6287029

Authors: Hong Chang, Zhong Huang, Xueliang Li, Yaping Mao, Haixing Zhao 

Publication date: 23 May 2017

Abstract: An edge-colored graph $G$ is emph{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 emph{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 $tgeq1$ and $ngeq2t+2$. Then we prove that $1leqcfc(G)leqn-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 $overlineG$ are connected, then $4leqcfc(G)+cfc(overlineG)leqn$ and $4leqcfc(G)cdotcfc(overlineG)leq2(n-2)$, and moreover, $cfc(G)+cfc(overlineG)=n$ or $cfc(G)cdotcfc(overlineG)=2(n-2)$ if and only if one of $G$ and $overlineG$ is a tree with maximum degree $n-2$ or a $P_5$, and the lower bounds are sharp.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Structural characterization of families of graphs (05C75)

This page was built for publication: Nordhaus-Gaddum-type theorem for conflict-free connection number of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6287029)