Monochromatic disconnection of graphs

Abstract

For an edge-colored graph $G$, we call an edge-cut $M$ of $G$ monochromatic if the edges of $M$ are colored with a same color. The graph $G$ is called monochromatically disconnected if any two distinct vertices of $G$ are separated by a monochromatic edge-cut. For a connected graph $G$, the monochromatic disconnection number, denoted by $md(G)$, of $G$ is the maximum number of colors that are needed in order to make $G$ monochromatically disconnected. We will show that almost all graphs have monochromatic disconnection numbers equal to 1. We also obtain the Nordhaus-Gaddum-type results for $md(G)$.

16 pages