论文标题
$ md $ numbers的上限和极端图的特征
Upper bounds for the $MD$-numbers and characterization of extremal graphs
论文作者
论文摘要
对于边缘颜色的图形$ g $，如果$ m $的边缘颜色相同，我们称为$ g $ $ g $单色。如果任何两个不同的$ g $的顶点被单色边缘切割分离，则图$ g $被称为单色断开。对于连接的图形$ g $，单色断开编号（或简称为$ md $ -number）的$ g $，用$ md（g）$表示，是允许的最大颜色数量，以使$ g $单色断开连接。对于直径1的图表，它们是完整的图形，因此它们的$ MD $ numbers为$ 1 $。对于直径至少3的图形，我们可以构造$ 2 $连接的图形，以便它们的$ MD $ -NUMBER可以任意大；而对于直径二的图形$ g $，我们表明，如果$ g $是$ 2 $连接的图，则$ md（g）\ leq 2 $，如果$ g $具有切割的vertex，则$ md（g）$等于$ g $的块数量。因此，我们将专注于研究直径二的$ 2 $连接图，并根据其连通性和独立数字分别给出其$ MD $ numbers的两个上限。我们还表征了$ \ left \ lfloor \ frac {n} {2} \ right \ rfloor $ - 连接的图（带有较大的连接性），其$ md $ -numbers为$ 2 $ an $\left\lfloor\frac{n}{2}\right\rfloor.$ For graphs with connectivity less than $\frac n 2$, 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）\ leq \ left \ lfloor \ frac {n} {k} \ right \ rfloor $。
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)\leq 2$, 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 $\left\lfloor\frac{n}{2}\right\rfloor$-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 $\left\lfloor\frac{n}{2}\right\rfloor.$ For graphs with connectivity less than $\frac n 2$, 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)\leq \left\lfloor\frac{n}{k}\right\rfloor$.
