Monochromatic disconnection of graphs

DOI10.1016/J.DAM.2020.08.032MaRDI QIDQ2208356zbMATH OpenOpenAlexFDO

Authors Ping Li, Xueliang Li

Publication date 2 November 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.01372

zbMATH Keywords

monochromatic disconnection numbermonochromatic edge-cutNordhaus-Gaddum-type results

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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)$.

Recommendations

• Monochromatic disconnection: Erdős-Gallai-type problems and product graphs
• Monochromatic vertex-disconnection colorings of graphs
• More on the rainbow disconnection in graphs
• Upper bounds for the \(M D\)-numbers and characterization of extremal graphs
• Rainbow disconnection in graphs

Cites work

• A note on Nordhaus-Gaddum inequalities for domination.
• A survey of Nordhaus-Gaddum type relations
• Colorful monochromatic connectivity
• Graph theory
• scientific article; zbMATH DE number 5015716 (Why is no real title available?)
• Monochromatic \(k\)-edge-connection colorings of graphs
• Nordhaus-Gaddum inequalities for domination in graphs
• Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs
• Nordhaus-Gaddum-type theorem for Wiener index of graphs when decomposing into three parts
• On Complementary Graphs
• On conflict-free connection of graphs
• Properly colored connectivity of graphs
• Rainbow connection in graphs
• Rainbow disconnection in graphs

Cited in

(8)

• Proper disconnection of graphs
• Further results on the rainbow vertex-disconnection of graphs
• Monochromatic vertex-disconnection colorings of graphs
• Monochromatic disconnection: Erdős-Gallai-type problems and product graphs
• Upper bounds for the \(M D\)-numbers and characterization of extremal graphs
• The proper vertex-disconnection of graphs
• Completely Disconnecting the Complete Graph
• Relations of three classes of disconnected coloring

This page was built for publication: Monochromatic disconnection of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2208356)