Back to Search
Start Over
Strong conflict-free connection of graphs.
- Source :
-
Applied Mathematics & Computation . Jan2020, Vol. 364, pN.PAG-N.PAG. 1p. - Publication Year :
- 2020
-
Abstract
- A path P in an edge-colored graph is called a conflict-free path if there exists a color used on only one of the edges of P. An edge-colored graph G is called conflict-free connected if for each pair of distinct vertices of G there is a conflict-free path in G connecting them. The graph G is called strongly conflict-free connected if for every pair of vertices u and v of G there exists a conflict-free path of length d G (u, v) in G connecting them. For a connected graph G , the strong conflict-free connection number of G , denoted by scfc (G), is defined as the smallest number of colors that are required in order to make G strongly conflict-free connected. In this paper, we first show that if G t is a connected graph with m (≥ 2) edges and t edge-disjoint triangles, then scfc (G t) ≤ m − 2 t , and the equality holds if and only if G t ≅ S m − t , t . Then we characterize the graphs G with s c f c (G) = k for k ∈ { 1 , m − 3 , m − 2 , m − 1 , m }. In the end, we present a complete characterization for the cubic graphs G with s c f c (G) = 2. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH connectivity
*GEOMETRIC vertices
*TRIANGLES
Subjects
Details
- Language :
- English
- ISSN :
- 00963003
- Volume :
- 364
- Database :
- Academic Search Index
- Journal :
- Applied Mathematics & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 138668371
- Full Text :
- https://doi.org/10.1016/j.amc.2019.124639