DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

T. Doan and I. Schiermeyer

Title:

Conflict-free vertex connection number at most 3 and size of graphs

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-08-18, Revised: 2019-02-27, Accepted: 2019-02-27, https://doi.org/10.7151/dmgt.2211

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 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)\geq 2$ for every connected graph on $n\geq 2$ vertices.<br>Our main result of this paper is the following. Let $G$ be a connected graph of order $n$. If $|E(G)|\geq{n-6\choose 2}+7$, then $vcfc(G)\leq3$. We also show that $vcfc(G)\leq 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.$

Keywords:

vertex-colouring, conflict-free vertex-connection number, size of graph

PDF
Close