Upper bounds for the $MD$-numbers and characterization of extremal graphs¹¹1Supported by NSFC No.11871034 and 11531011.

Let $G=G_{1}\cup G_{2}$ and $\Gamma$ be an extremal $MD$-coloring of $G$. Then $|\Gamma(G_{1}\cap G_{2})|=1$ and $\Gamma$ is an $MD$-coloring restricted on $G_{1}$ (and also $G_{2}$). So, $md(G_{1}\cup G_{2})=|\Gamma(G_{1})|+|\Gamma(G_{2})|-|\Gamma(G_{1}\cap G_{2})|\leq md(G_{1})+md(G_{2})-1$. On the other hand, since $E(G_{1}\cap G_{2})$ is monochromatic under any $MD$-coloring of $G_{1}\cup G_{2}$, let $\Gamma_{i}$ be an $MD$-coloring of $G_{i}$ for $i\in[2]$ such that $\Gamma_{1}(G_{1}\cap G_{2})=\Gamma_{2}(G_{1}\cap G_{2})=\Gamma(G_{1})\cap\Gamma(G_{2})$. Let $\Gamma^{\prime}$ be an edge-coloring of $G_{1}\cup G_{2}$ such that $\Gamma^{\prime}(e)=\Gamma_{i}(e)$ if $e\in E(G_{i})$, and let $w$ be a vertex of $G_{1}\cap G_{2}$. Then for any two vertices $u,v$ of $G_{1}\cup G_{2}$, if $u,v\in V(G_{i})$, then $C_{\Gamma_{i}}(u,v)\subseteq C_{\Gamma^{\prime}}(u,v)$; if $u\in V(G_{1})-V(G_{2})$ and $v\in V(G_{2})-V(G_{1})$, then $(C_{\Gamma_{1}}(u,w)\cup C_{\Gamma_{2}}(v,w))\subseteq C_{\Gamma^{\prime}}(u,v)$. So, $\Gamma^{\prime}$ is an $MD$-coloring of $G$, i.e., $md(G_{1}\cup G_{2})\geq|\Gamma(G_{1}\cup G_{2})|=md(G_{1})+md(G_{2})-1$. Therefore, $md(G_{1}\cup G_{2})=md(G_{1})+md(G_{2})-1$.  

Let $\Gamma$ be an extremal $MD$-coloring of $G$. Let $||P||=t$ and let $P=ae_{1}c_{1}\cdots e_{t}b$. Let $\Gamma^{\prime}$ be an edge-coloring of $G^{\prime}$ such that $\Gamma(f)=\Gamma^{\prime}(f)$ when $f\in E(G)-e$, $\Gamma^{\prime}(e_{i})=\Gamma^{\prime}(e_{t+1-i})=|\Gamma(G)|+i$ for $i\in[\left\lfloor\frac{t-1}{2}\right\rfloor]$, $\Gamma(e)=\Gamma^{\prime}(e_{\frac{t+1}{2}})$ when $t$ is odd, and $\Gamma(e)=\Gamma^{\prime}(e_{\frac{t}{2}})=\Gamma^{\prime}(e_{\frac{t}{2}+1})$ when $t$ is even. It is easy to verify that $\Gamma^{\prime}$ is an $MD$-coloring of $G^{\prime}$. Thus, $md(G^{\prime})\geq md(G)+\left\lfloor\frac{||P||-1}{2}\right\rfloor$.  

Let $H_{i}$ be the graph obtained from $G$ by deleting all the edges with color $i$. Let $G^{\prime}=G\cup e$. If $\Gamma^{\prime}$ is not an $MD$-coloring of $G^{\prime}$, then there are two vertices $x,y$ of $G^{\prime}$ such that $C_{\Gamma^{\prime}}(x,y)=\emptyset$. If $t\in C_{\Gamma}(x,y)$, since $x,y$ are in different components of $H_{t}$, we have $t\in C_{\Gamma^{\prime}}(x,y)$, a contradiction. If $t\notin C_{\Gamma}(x,y)$, then let $j\in C_{\Gamma}(x,y)$. Then there are two components $D_{1},D_{2}$ of $H_{j}$ such that $x\in V(D_{1})$ and $y\in V(D_{2})$. Since $j$ does not separate $x,y$ in $G^{\prime}$, the edge $e$ connects $D_{1}$ and $D_{2}$, say $u\in V(D_{1})$ and $v\in V(D_{2})$. Thus, the color $j$ separates $u,v$ in $G$, which contradicts that $C_{\Gamma}(u,v)=\{t\}$. Therefore, $\Gamma^{\prime}$ is an $MD$-coloring of $G^{\prime}$. Since $|\Gamma^{\prime}(G^{\prime})|=|\Gamma(G)|$ and $\Gamma$ is an extremal $MD$-coloring of $G$, we have $md(G^{\prime})\geq md(G)$. Since $G$ is a connected spanning subgraph of $G^{\prime}$, by Lemma 1.1 (3) we have $md(G)\geq md(G^{\prime})$. So, $md(G)=md(G^{\prime})$.  

The proof of statement (1) goes as follows. If $v$ is a cut-vertex of $G$ and $diam(G)=2$, then $v$ connects every vertex of $V(G-v)$. Thus, for each block $D$ of $G$, $D-v$ is connected and $D=(D-v)\vee v$, i.e., $md(D)=1$. Therefore, $md(G)$ is equal to the number of blocks of $G$.

Next, for the proof of statement (2) suppose $\Gamma$ is an $MD$-coloring of $G$ with $|\Gamma(G)|\geq 3$. Then each hypercycle (hyperpath) of the above mentioned hypergraph $\mathcal{H}_{\Gamma}$ is a linear hypercycle (linear hyperedge). We now prove that there is a rainbow hyper $3$-path (the colors of the three hyperedges are pairwise differently) in $\mathcal{H}_{\Gamma}$. Since $\mathcal{H}_{\Gamma}$ does not have hyper $3$-cycle, the union of three consecutive hyperedges forms a hyper $3$-path. If every vertex $z$ of $G$ has $d^{c}(z)\leq 2$, then there is a rainbow hyper $3$-path in $\mathcal{H}_{\Gamma}$. If there is a vertex $x$ of $G$ with $d^{c}(x)\geq 3$, then there are three hyperedges, say $D_{1},D_{2}$ and $D_{3}$, such that $x$ is the common vertex of them. Then the colors of $D_{1},D_{2}$ and $D_{3}$ are pairwise differently. Since $G$ is a $2$-connected graph, there is a vertex $w$ of $V(D_{1})-\{x\}$ with $d^{c}(w)\geq 2$ (otherwise, $x$ is a cut-vertex of $G$, a contradiction). Then there is a hyperedge $F$ of $G$, such that $w$ is a common vertex of $F$ and $D_{1}$. Thus, either $F\cup D_{1}\cup D_{2}$ or $F\cup D_{1}\cup D_{3}$ is a rainbow hyper $3$-path.

Let $\mathcal{P}$ be a rainbow hyper $3$-path of $\mathcal{H}$ and let $V(D_{i})\cap V(D_{i+1})=\{u_{i}\}$ for $i\in[2]$. Let $u\in V(D_{1})-\{u_{1}\}$ and $v\in V(D_{3})-\{u_{2}\}$. We use $\mathcal{P}_{u,v}$ to denote a minimum hyperpath connecting $u$ and $v$. Since $diam(G)=2$, the size of $\mathcal{P}_{u,v}$ is either one or two. Let $\mathcal{C}=\mathcal{P}_{u,v}\cup\mathcal{P}$. If $\mathcal{P}_{u,v}$ is a hyperedge, then $\mathcal{C}$ is a hyper $4$-cycle. Since $D_{1}$ and $D_{3}$ are opposite hyperedges of $\mathcal{C}$ and they have different colors, a contradiction. If $\mathcal{P}_{u,v}$ is a hyper $2$-path, then let $F_{1},F_{2}$ be hyperedges of $\mathcal{P}_{u,v}$, and let $V(F_{1})\cap V(F_{2})=\{u_{3}\}$. If $u_{3}\notin\{u_{1},u_{2}\}$, then $\mathcal{C}$ is a hyper $5$-cycle, a contradiction. If $u_{3}\in\{u_{1},u_{2}\}$, then $\mathcal{C}$ contains a hyper $3$-cycle, a contradiction.

Finally, we show statement (3). It is obvious that $diam(G)\leq 2$, and $G$ is a $2$-connected graph when $n\geq 3$. So, $md(G)\leq 2$. Suppose $G=K_{s}\Box K_{t}$ and $s,t\geq 2$. Then $|N(u,v)|=2$ for any nonadjacent vertices $u$ and $v$ of $G$. By Lemma 1.1 (2) and Theorem 1.3, we have $md(G)=md(K_{s})+md(K_{t})=2$.

Suppose $md(G)=2$. Then $n\geq 3$ and $G$ is a $2$-connected graph. Let $\Gamma$ be an extremal $MD$-coloring of $G$ and let $G_{1},G_{2}$ be the colors $1,2$ induced subgraphs of $G$, respectively. Since $md(G)=2$, we have $d^{c}(v)\leq 2$ for each $v\in V(G)$. If $d^{c}(v)=1$, by symmetry, suppose $v$ is in a component $D$ of $G_{1}$. Since $md(G)=2$, we have $D\neq G$, i.e., there exists a vertex $u$ in $V(G)-V(D)$. Then $u,v$ are nonadjacent and $N(u,v)\subseteq D$. Let $\{a,b\}\subseteq N(u,v)$. Since $\Gamma(va)=\Gamma(vb)=1$, we have $va\cup vb\cup ua\cup ub$ is a monochromatic $4$-cycle, i.e., $u\in V(D)$, a contradiction. Thus, $d^{c}(v)=2$ for each $v\in V(G)$. We use $D_{u}^{1}$ and $D_{u}^{2}$ to denote the components of $G_{1}$ and $G_{2}$, respectively, such that $V(D_{u}^{1})\cup V(D_{u}^{2})=u$.

Suppose there are $t$ components of $G_{1}$ and $s$ components of $G_{2}$. Since $G$ is a $2$-connected graph, we have $s,t\geq 2$. Otherwise, if $s=1$, then for each vertex $v$ of $G_{1}$, $v$ is a cut-vertex, a contradiction. We label the $t$ components of $G_{1}$ by the numbers in $[t]$ and label the $s$ components of $G_{2}$ by the numbers in $[s]$, respectively. We use $l_{1}(D)$ to denote the label of a component $D$ of $G_{1}$, and use $l_{2}(F)$ to denote the label of a component $F$ of $G_{2}$. For a vertex $u$ of $G$, since $d^{c}(u)=2$, we use $(l_{1}(D_{u}^{1}),l_{2}(D_{u}^{2}))$ to denote $u$. For two vertices $u,v$ of $G$, let $u=(i,j)$ and let $v=(s,t)$. In order to show $G=K_{s}\Box K_{t}$, we need to show that $uv$ is an edge of $G$ when $i=s$ and $j\neq t$, or $i\neq s$ and $j=t$, and $u,v$ are nonadjacent vertices when $i\neq s$ and $j\neq t$. If $i\neq s$ and $j\neq t$, then $v\notin V(D_{u}^{1}\cup D_{u}^{2})$. Since $N(u)\subseteq V(D_{u}^{1}\cup D_{u}^{2})$, $u,v$ are nonadjacent vertices of $G$. If, by symmetry, $i=s$ and $j\neq t$, then $D_{u}^{1}=D_{v}^{1}$. Let $u^{\prime}\in V(D_{u}^{2})-\{u\}$. Then $u^{\prime},v$ are nonadjacent. Since $N(v)\subseteq V(D_{v}^{1}\cup D_{v}^{2})$ and $N(u^{\prime})\subseteq V(D_{u^{\prime}}^{1}\cup D_{u^{\prime}}^{2})$, we have

Thus, $D_{v}^{1}\cap D_{u^{\prime}}^{2}\subseteq N(v,u^{\prime})$. Since $D_{v}^{1}\cap D_{u^{\prime}}^{2}=\{u\}$, we have $uv$ is an edge of $G$.  

Since $N(x)+N(y)\geq n-1$ for any two nonadjacent vertices $x$ and $y$, we have $diam(G)\leq 2$. So, $md(G)\leq 2$.

It is obvious that $G$ is a $\left\lfloor\frac{n}{2}\right\rfloor$-connected graph if $G=A_{n}$ or $G\in\mathcal{A}_{n}$. Moreover, by Lemma 1.4 and Theorem 3.1, we have $md(G)=2$.

Now suppose $G$ is a $\left\lfloor\frac{n}{2}\right\rfloor$-connected graph and $md(G)=2$. Since $n\geq 4$, $G$ is a $2$-connected graph. We distinguish the following cases for our proof.

Case 1. $n$ is even.

For any two nonadjacent vertices $u,v$ of $G$, $|N(u)\cap N(v)|\geq 2$. By Theorem 3.1 (3), $G=K_{s}\Box K_{t}$, where $s,t\geq 2$. We need to prove that at least one of $s,t$ equals two. Suppose $H_{1},H_{2}$ are two cliques of order $s,t$, respectively, and $V(H_{1})\cap V(H_{2})=\{u\}$. Then $N(u)\subseteq V(H_{1}\cup H_{2})$, i.e., $s+t-2\geq\frac{n}{2}$. Since $n=st$, we have $t(s-2)\leq 2(s-2)$. Thus, either $s=2$ or $t=2$.

Case 2. $n$ is odd.

Say $n=2k+1$ for some integer $k$. Suppose $\Gamma$ is an extremal $MD$-coloring of $G$ and $G_{1},G_{2}$ are the colors $1,2$ induced subgraphs, respectively.

Subcase 2.1 Every vertex $v$ of $G$ has $d^{c}(v)=2$.

Suppose there are components $D,F$ of $G_{1},G_{2}$, respectively, such that $V(G)\cap V(F)=\emptyset$. Then let $u\in V(D)$ and $v\in V(F)$. Since $d^{c}(u)=d^{c}(v)=2$, there are components $D^{\prime}$ of $G_{1}$ and $F^{\prime}$ of $G_{2}$, such that $V(D)\cap V(F^{\prime})=\{u\}$ and $V(F)\cap V(D^{\prime})=\{v\}$. Since $V(D)\cup V(F^{\prime})-\{u\}$ and $V(D^{\prime})\cup V(F)-\{v\}$ are vertex-cuts of $G$, we have $|V(D)\cup V(F^{\prime})|\geq k+1$ and $|V(D^{\prime})\cup V(F)|\geq k+1$. Since $|V(D^{\prime})\cap V(F^{\prime})|\leq 1$, we have $n\geq|V(D)\cup V(F^{\prime})|+|V(D^{\prime})\cup V(F)|-|V(D^{\prime})\cap V(F^{\prime})|\geq 2k+1=n$, i.e., $D\cup D^{\prime}\cup F\cup F^{\prime}=G$. Then $u$ is a cut-vertex of $G$, a contradiction. Therefore, for each component $D$ of $G_{1}$ and each component $F$ of $G_{2}$, we have $|V(G)\cap V(F)|=1$. Then since $d^{c}(v)=2$ for each $v\in V(G)$, any two components of $G_{1}$ (and also $G_{2}$) have the same order, say $s$ (the order is $t$). Then $s,t>2$; otherwise, suppose $s=2$, i.e., $G_{1}$ is a matching. Since $n$ is odd, we have $V(G)-V(G_{1})\neq\emptyset$. Thus, each vertex $v$ of $V(G)-V(G_{1})$ has $d^{c}(v)=1$, a contradiction. For a vertex $x$ of $G$, let $D_{1},D_{2}$ be the components of $G_{1},G_{2}$, respectively, containing $x$. Then $D_{1}\cup D_{2}-\{x\}$ is a vertex-cut of $G$, i.e., $s+t-2\geq k$. However, $2k+1=n=st$ and $s,t>3$, a contradiction.