Publications
Sort:
Open Access Research Article Issue
Results on monochromatic vertex disconnection of graphs
AIMS Mathematics 2023, 8(6): 13219-13240
Published: 15 June 2023
Abstract PDF (2.9 MB) Collect
Downloads:1

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 m v d ( 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: m v d ( G ), connectivity and block decomposition. We determine the value of m v d ( G ) for some well-known graphs, and then characterize G when n 5 m v d ( G ) n and all blocks of G are minimally 2-connected triangle-free graphs. We obtain the maximum size of a graph G with m v d ( G ) = k for any k. Finally, we study the Erdős-Gallai-type results for m v d ( G ), and completely solve them.

Total 1