{
  "id": "2009.00222",
  "version": "v1",
  "published": "2020-09-01T04:43:54.000Z",
  "updated": "2020-09-01T04:43:54.000Z",
  "title": "Upper bounds for the $MD$-numbers and characterization of extremal graphs",
  "authors": [
    "Ping Li",
    "Xueliang Li"
  ],
  "comment": "21 pages",
  "categories": [
    "math.CO"
  ],
  "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)\\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 graphs with connectivities 2 (small) and at least $\\left\\lfloor\\frac{n}{2}\\right\\rfloor$ (large) 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$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-09-01T04:43:54.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C40",
      "05C35"
    ],
    "keywords": [
      "upper bound",
      "connected graph",
      "extremal graphs",
      "connectivity",
      "characterization"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}