论文标题
图形的单色顶点隔间
Monochromatic vertex-disconnection of graphs
论文作者
论文摘要
令G为顶点图。如果s的顶点用相同的颜色颜色，则g的顶点切割s被称为单色顶点切割。如果g的任何两个非附属顶点具有单色的单色顶点，则将图G分为单色。 g的单色顶点 - 隔间数，用MVD（g）表示，是用于使G单色的最大颜色数量。在本文中，研究了图参数之间的连接：MVD（G），连接性和块分解。我们确定了一些众所周知的图表的MVD（G）值，然后在N-5 \ leq MVD（G）\ Leq N和G的所有块中表征G，而G的所有块都是最小的2个连接的三角形图。对于任何K，我们获得具有MVD（G）= K的图G的最大尺寸。此外，我们研究了MVD（G）的Erdős-Gallai型结果，并完全解决了它们。最后，我们提出了一种计算MVD（G）的算法，并给出G的MVD颜色。
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 has 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\leq mvd(G)\leq 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. Furthermore, we study the Erdős-Gallai-type results for mvd(G), and completely solve them. Finally, we propose an algorithm to compute mvd(G) and give an mvd-coloring of G.
