Results on monochromatic vertex disconnection of graphs - Miao Fu; Yuqin Zhang (AIMS Mathematics, 2023)
Let $ G $ be a vertex-colored graph. A vertex cut $ S $ of $ G $ is called a monochromatic vertex cut if the vertices of $ S $ are colored with the same color. A graph $ G $ is monochromatically vertex-disconnected if any two nonadjacent vertices of $ G $ have a monochromatic vertex cut separating them. The monochromatic vertex disconnection number of $ G $, denoted by $ mvd(G) $, is the maximum number of colors that are used to make $ G $ monochromatically vertex-disconnected. In this paper, the connection between the graph parameters are studied: $ mvd(G) $, connectivity and block decomposition. We determine the value of $ mvd(G) $ for some well-known graphs, and then characterize $ G $ when $ n-5≤ mvd(G)≤ n $ and all blocks of $ G $ are minimally 2-connected triangle-free graphs. We obtain the maximum size of a graph $ G $ with $ mvd(G) = k $ for any $ k $. Finally, we study the Erdős-Gallai-type results for $ mvd(G) $, and completely solve them.