pith. sign in

arxiv: 1503.08941 · v1 · pith:6FQYZYZ2new · submitted 2015-03-31 · 🧮 math.CO

Some extremal results on the colorful monochromatic vertex-connectivity of a graph

classification 🧮 math.CO
keywords emphgraphmonochromaticnumberpathvertex-connectioncolorfulmvc-coloring
0
0 comments X
read the original abstract

A path in a vertex-colored graph is called a \emph{vertex-monochromatic path} if its internal vertices have the same color. A vertex-coloring of a graph is a \emph{monochromatic vertex-connection coloring} (\emph{MVC-coloring} for short), if there is a vertex-monochromatic path joining any two vertices in the graph. For a connected graph $G$, the \emph{monochromatic vertex-connection number}, denoted by $mvc(G)$, is defined to be the maximum number of colors used in an \emph{MVC-coloring} of $G$. These concepts of vertex-version are natural generalizations of the colorful monochromatic connectivity of edge-version, introduced by Caro and Yuster. In this paper, we mainly investigate the Erd\H{o}s-Gallai-type problems for the monochromatic vertex-connection number $mvc(G)$ and completely determine the exact value. Moreover, the Nordhaus-Gaddum-type inequality for $mvc(G)$ is also given.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.