Monochromatic disconnection: Erdős-Gallai-type problems and product 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. The monochromatic disconnection number, denoted by $md(G)$, of a connected graph $G$ is the maximum number of colors that are allowed to make $G$ monochromatically disconnected. In this paper, we solve the Erdős-Gallai-type problems for the monochromatic disconnection, and give the monochromatic disconnection numbers for four graph products, i.e., Cartesian, strong, lexicographic, and tensor products.

21 pages, 4 figures. In this new version we obtain the explicit expression for the extremal function $g(n,r)$, which was only an upper bound for the case $3\le r\le \lfloor \frac{n}{2}\rfloor -1$ in the old version