- Tytuł:
- Conflict-Free Vertex Connection Number at Most 3 and Size of Graphs
- Autorzy:
-
Doan, Trung Duy
Schiermeyer, Ingo - Powiązania:
- https://bibliotekanauki.pl/articles/32083899.pdf
- Data publikacji:
- 2021-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
vertex-colouring
conflict-free vertex-connection number
size of graph - Opis:
- 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 a 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. Clearly, $vcfc(G) ≥ 2$ for every connected graph on $n ≥ 2$ vertices. Our main result of this paper is the following. Let $G$ be a connected graph of order $n$. If \(|E(G)|≥\binom{n-6}{2}+7\), then $vcfc(G) ≤ 3$. We also show that $vcfc(G) ≤ k + 3 − t$ for every connected graph $G$ with $k$ cut-vertices and $t$ being the maximum number of cut-vertices belonging to a block of $G$.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 617-632
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł