Back to Search
Start Over
The Conflict-Free Vertex-Connection Number and Degree Conditions of Graphs.
- Source :
- Graphs & Combinatorics; Oct2022, Vol. 38 Issue 5, p1-15, 15p
- Publication Year :
- 2022
-
Abstract
- A path in a vertex-coloured graph is called conflict-free if there is a colour used on exactly one of its vertices. A vertex-coloured graph is said to be conflict-free vertex-connected if any two distinct vertices of the graph are connected by at least one conflict-free vertex-path. The conflict-free vertex-connection number, denoted by vcfc(G), is the smallest number of colours needed in order to make G conflict-free vertex-connected. Our main result of this paper is the following: Let G be a connected graph of order n ≥ 11 . If δ (G) ≥ n 5 , then v c f c (G) ≤ 3 . Moreover, we show that both bounds, on the order n and the minimum degree δ (G) , are tight. Furthermore, we generalize our result by requiring minimum degree-sum conditions for pairs, triples or quadruples of independent vertices. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 09110119
- Volume :
- 38
- Issue :
- 5
- Database :
- Complementary Index
- Journal :
- Graphs & Combinatorics
- Publication Type :
- Academic Journal
- Accession number :
- 159067758
- Full Text :
- https://doi.org/10.1007/s00373-022-02567-y