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

preprint2015arXivOpen access

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 GG, the \emph{monochromatic vertex-connection number}, denoted by mvc(G)mvc(G), is defined to be the maximum number of colors used in an \emph{MVC-coloring} of GG. 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ős-Gallai-type problems for the monochromatic vertex-connection number mvc(G)mvc(G) and completely determine the exact value. Moreover, the Nordhaus-Gaddum-type inequality for mvc(G)mvc(G) is also given.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.