Some extremal results on the colorful monochromatic vertex-connectivity of a graph |
| |
Authors: | Qingqiong Cai Xueliang Li Di Wu |
| |
Institution: | 1.Center for Combinatorics and LPMC,Nankai University,Tianjin,China |
| |
Abstract: | A path in a vertex-colored graph is called a vertex-monochromatic path if its internal vertices have the same color. A vertex-coloring of a graph is a monochromatic vertex-connection coloring (MVC-coloring for short), if there is a vertex-monochromatic path joining any two vertices in the graph. For a connected graph G, the monochromatic vertex-connection number, denoted by mvc(G), is defined to be the maximum number of colors used in an 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 (Discrete Math 311:1786–1792, 2011). In this paper, we mainly investigate the Erd?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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|