Conflict-free connection numbers of line graphs

DOI10.1007/978-3-319-71150-8_14MaRDI QIDQ1699775zbMATH OpenOpenAlexFDO

Authors Bo Deng, Yaping Mao, Wenjing Li, Xueliang Li, Haixing Zhao

Publication date 26 February 2018

Full work available at URL https://arxiv.org/abs/1705.05317

zbMATH Keywords

\(K\)-iterated line graphsclaw-free graphsconflict-free connection numberline graphs

Mathematics Subject Classification ID

Connectivity (05C40) Graph operations (line graphs, products, etc.) (05C76)

Abstract: A path in an edge-colored graph is called emph{conflict-free} if it contains at least one color used on exactly one of its edges. An edge-colored graph $G$ is emph{conflict-free connected} if for any two distinct vertices of $G$, there is a conflict-free path connecting them. For a connected graph $G$, the emph{conflict-free connection number} of $G$, denoted by $cfc(G)$, is defined as the minimum number of colors that are required to make $G$ conflict-free connected. In this paper, we investigate the conflict-free connection numbers of connected claw-free graphs, especially line graphs. We first show that for an arbitrary connected graph $G$, there exists a positive integer $k$ such that $cfc(L^k(G))leq2$. Secondly, we get the exact value of the conflict-free connection number of a connected claw-free graph, especially a connected line graph. Thirdly, we prove that for an arbitrary connected graph $G$ and an arbitrary positive integer $k$, we always have $cfc(L^{k+1}(G))leqcfc(L^k(G))$, with only the exception that $G$ is isomorphic to a star of order at least~$5$ and $k=1$. Finally, we obtain the exact values of $cfc(L^k(G))$, and use them as an efficient tool to get the smallest nonnegative integer $k_0$ such that $cfc(L^{k_0}(G))=2$.

Recommendations

• Conflict-free connections of graphs
• Erdős-Gallai-type results for conflict-free connection of graphs.
• Graphs with conflict-free connection number two
• On conflict-free connection of graphs
• Conflict-free connection number and size of graphs

Cited in

(14)

• Conflict-free connections of graphs
• On conflict-free connection of graphs
• Graphs with conflict-free connection number two
• Conflict-free connection number and independence number of a graph
• Conflict-free connection number and size of graphs
• Conflict-free connection of trees
• Conflict-free connection number of random graphs
• Hardness results for three kinds of colored connections of graphs
• Conflict-free vertex-connections of graphs
• (Strong) conflict-free connectivity: algorithm and complexity
• Some results on strong conflict-free connection number of graphs
• Conflict-free (vertex-)connection numbers of graphs with small diameters
• Conflict-free connection number of graphs with four bridges
• A survey on conflict-free connection coloring of graphs

This page was built for publication: Conflict-free connection numbers of line graphs

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