Upper bounds for the M D-numbers and characterization of extremal graphs

DOI10.1016/J.DAM.2021.02.023MaRDI QIDQ2661209zbMATH OpenOpenAlexFDO

Authors Ping Li, Xueliang Li

Publication date 1 April 2021

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

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

zbMATH Keywords

connectivitydiameterextremal graphindependent numbermonochromatic disconnection numberupper bound

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Connectivity (05C40)

Abstract: For an edge-colored graph $G$, we call an edge-cut $M$ of $G$ monochromatic if the edges of $M$ are colored with the same color. The graph $G$ is called monochromatic disconnected if any two distinct vertices of $G$ are separated by a monochromatic edge-cut. For a connected graph $G$, the monochromatic disconnection number (or $MD$-number for short) of $G$, denoted by $md(G)$, is the maximum number of colors that are allowed in order to make $G$ monochromatic disconnected. For graphs with diameter one, they are complete graphs and so their $MD$-numbers are $1$. For graphs with diameter at least 3, we can construct $2$-connected graphs such that their $MD$-numbers can be arbitrarily large; whereas for graphs $G$ with diameter two, we show that if $G$ is a $2$-connected graph then $md(G)leq2$, and if $G$ has a cut-vertex then $md(G)$ is equal to the number of blocks of $G$. So, we will focus on studying $2$-connected graphs with diameter two, and give two upper bounds of their $MD$-numbers depending on their connectivity and independent numbers, respectively. We also characterize the $leftlfloorfracn2ightfloor$-connected graphs (with large connectivity) whose $MD$-numbers are $2$ and the $2$-connected graphs (with small connectivity) whose $MD$-numbers archive the upper bound $leftlfloorfracn2ightfloor.$ For graphs with connectivity less than $fracn2$, we show that if the connectivity of a graph is in linear with its order $n$, then its $MD$-number is upper bounded by a constant, and this suggests us to leave a conjecture that for a $k$-connected graph $G$, $md(G)leqleftlfloorfracnkightfloor$.

Recommendations

• Monochromatic disconnection of graphs
• Monochromatic disconnection: Erdős-Gallai-type problems and product graphs
• Extremal graphs with maximum monochromatic connectivity
• The monochromatic connectivity of graphs
• Colorful monochromatic connectivity

Cites work

• Average distance and vertex-connectivity
• Colorful monochromatic connectivity
• Complexity results for the proper disconnection of graphs
• Edge-vulnerability and mean distance
• Graph theory
• Monochromatic disconnection of graphs
• On the sum of all distances in a graph or digraph
• Proper connection of graphs
• Proper disconnection of graphs
• Proper‐walk connection number of graphs
• Rainbow connection in graphs
• Rainbow disconnection in graphs

Cited in

(5)

• Monochromatic vertex-disconnection colorings of graphs
• Monochromatic disconnection: Erdős-Gallai-type problems and product graphs
• Monochromatic disconnection of graphs
• The proper vertex-disconnection of graphs
• Relations of three classes of disconnected coloring

This page was built for publication: Upper bounds for the \(M D\)-numbers and characterization of extremal graphs

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