Weak External Bisection of Some Graphs

Yumin Liu^1,2

¹Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou, China.
²Department of Mathematics, Lishui University, Lishui, China.

DOI: 10.4236/jamp.2024.121009                

Abstract

Let G be a graph. A bipartition of G is a bipartition of V (G) with V (G) = V₁ ∪ V₂ and V₁ ∩ V₂ = ∅. If a bipartition satisfies ∥V₁∣ - ∣V₂∥ ≤ 1, we call it a bisection. The research in this paper is mainly based on a conjecture proposed by Bollobás and Scott. The conjecture is that every graph G has a bisection (V₁, V₂) such that ∀v ∈ V₁, at least half minuses one of the neighbors of v are in the V₂; ∀v ∈ V₂, at least half minuses one of the neighbors of v are in the V₁. In this paper, we confirm this conjecture for some bipartite graphs, crown graphs and windmill graphs.

Keywords

Weak External Bisection, Bipartite Graph, Windmill Graph

1. Introduction

Let G be a graph with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$ . An external bipartition of G is $V\left(G\right)=V_1\cup V_2$ and $V_1\cap V_2=\varnothing$ and requires that at least half of the neighbors of each vertex are in the other part. If a bipartition satisfies $\left|\left|V_1\right|-\left|V_2\right|\right|\le 1$ , we call it a bisection and denote it by $\left(V_1,V_2\right)$ . Ban and Linial [1] showed that every class 1, 3 or 4 regular graph G has an external bisection. Bollobás and Scott [2] observed that not every graph has an external bisection. In the same paper, they gave a counterexample that $K_{2l+1,m}$ , where $m\ge 2l+3$ doesn’t have an external bisection. Esperet, Mazzuoccolo and Tarsi [3] found a set of cubic graphs without external bisection and containing at least 2 bridges.

For vertices $u,v\in V\left(G\right)$ , if $uv\in E\left(G\right)$ , then edge uv is said to be associated with u and v. The degree of v is the number of edges in G associated with v, denoted as $d\left(v\right)$ . Let $\left(V_1,V_2\right)$ be a bisection of G. For a vertex v in V₁, the internal degree of v is the number of the edges associated with v and other endpoints of these edges are in V₁ too; and the external degree of v is the number of the edges associated with v and other endpoints of these edges are in V₂. For a vertex v in V₂, the internal degree of v is the number of the edges associated with v and other endpoints of these edges are in V₂; and the external degree of v is the number of the edges associated with v and other endpoints of these edges are in V₁. The internal degree of v is denoted as $d_{in}\left(v\right)$ and the external degree of v is denoted as $d_{ex}\left(v\right)$ .

A graph is said to be a bipartite graph, denoted by $G\left[X,Y\right]$ , if the set of vertices of the graph can be partitioned into two non-empty subsets X and Y such that no two vertices in X are connected to each other with an edge and no two vertices in Y are connected with an edge.

The crown graph of [4] $G_{n,m}$ satisfies the condition:

$V\left(G_{n,m}\right)=\left\{u_i|i=1,2,\cdots ,n\right\}\cup \left\{v_i|i=1,2,\cdots ,n\right\}\underset{i=1}{\overset{n}{\cup }}\left\{u_{ij}|j=1,2,\cdots ,m\right\}$ ;

$\begin{array}{l}E\left(G_{n,m}\right)=\left\{u_1{u}_2,u_2{u}_3,\cdots ,u_n{u}_1\right\}\cup \left\{v_1{v}_2,v_2{v}_3,\cdots ,v_n{v}_1\right\}\cup \left\{v_1{u}_1,v_2{u}_2,\cdots ,v_n{u}_n\right\}\\ \underset{i=1}{\overset{n}{\cup }}\left\{u_i{u}_{ij}|j=1,2,\cdots ,m\right\}\underset{i=1}{\overset{n}{\cup }}\left\{u_{ij}{u}_{i\left(j+1\right)}|j=1,2,\cdots ,m-1\right\},\left(n\ge 3,m\ge 1\right).\end{array}$

For example, Figure 1 shows $G_{3,3}$ .

A windmill graph $K_m^{\left(n\right)}$ is a graph consisting of n m-order complete graphs $K_m$ with a common vertex.

For example, Figure 2 shows $K_4^{\left(n\right)}$ .

Conjecture 1.1. (Bollobás and Scott [2] ). Every graph G has a weak external bisection that is G has a bisection $\left(V_1,V_2\right)$ , such that:

$d_{ex}\left(v\right)\ge d_{in}\left(v\right)-1$ for all $v\in V\left(G\right)$ .

Figure 1. $G_{3,3}$ .

Figure 2. $K_4^{\left(n\right)}$ .

Ji, Ma, Yan and Yu [5] showed that every graphic sequence has a realization for which Conjecture 1.1 holds. In the same paper, they gave an infinite family of counterexamples to Conjecture 1.1.

In this paper, we confirm this conjecture for some graphs by showing the following three theorems.

Theorem 1.1. Let $G\left[X,Y\right]$ be a bipartite graph with $\left|X\right|=3$ , then $G\left[X,Y\right]$ admits a weak external bisection.

Theorem 1.2. Every crown graph $G_{n,m}$ admits a weak external bisection.

Theorem 1.3. Every windmill graph $K_m^{\left(n\right)}$ admits a weak external bisection.

In fact, by the proof Theorem 1.2, $G_{n,m}$ admits an external bisection.

2. Weak External Bisection

In this section, we prove Theorem 1.1, Theorem 1.2 and Theorem 1.3.

Proof of Theorem 1.1. Let $G\left[X,Y\right]$ be a bipartite graph with two parts X and Y, we define $Y_S=\left\{y\in Y|N\left(y\right)=S,S\subseteq X\right\}$ .

For a set S, we define a function:

$f\left(S\right)=\{\begin{array}{l}1\text{if}\left|S\right|\text{isodd;}\\ 0\text{if}\left|S\right|\text{iseven}\text{.}\end{array}$ (1)

Let $X=\left\{v_1,v_2,v_3\right\}$ , and assume, without loss of generality, that:

$\left|Y_{\left\{v_1,v_3\right\}}\right|\ge \left|Y_{\left\{v_1,v_2\right\}}\right|\ge \left|Y_{\left\{v_2,v_3\right\}}\right|$ .

Otherwise, we can re-label the three vertices in X. We give a weak external bisection $\left(V_1,V_2\right)$ of $V\left(G\right)$ by three steps.

First, let $\left\{v_1,v_2\right\}\subseteq V_1$ , $\left\{v_3\right\}\subseteq V_2$ , $Y_{\left\{v_1,v_2\right\}}\subseteq V_2$ and $Y_{\left\{v_1,v_3\right\}}^{*}\subseteq V_1$ where $Y_{\left\{v_1,v_3\right\}}^{*}\subseteq Y_{\left\{v_1,v_3\right\}}$ and $\left|Y_{\left\{v_1,v_3\right\}}^{*}\right|=\left|Y_{\left\{v_1,v_2\right\}}\right|$ . Because $\left|Y_{\left\{v_1,v_3\right\}}\right|\ge \left|Y_{\left\{v_1,v_2\right\}}\right|$ , such $Y_{\left\{v_1,v_3\right\}}^{*}$ exists. Let $Y_{\left\{v_1,v_3\right\}}^{**}=Y_{\left\{v_1,v_3\right\}}\backslash Y_{\left\{v_1,v_3\right\}}^{*}$ .

Then, we partition the odd sets of $Y_{\left\{v_2\right\}}$ , $Y_{\left\{v_1\right\}}$ , $Y_{\left\{v_1,v_3\right\}}^{**}$ , $Y_{\left\{v_1,v_2,v_3\right\}}$ , $Y_{\left\{v_2,v_3\right\}}$ , $Y_{\left\{v_3\right\}}$ one after another. Denote by $S_1,S_2,\cdots ,S_m$ , the odd sets of $Y_{\left\{v_2\right\}}$ , $Y_{\left\{v_1\right\}}$ , $Y_{\left\{v_1,v_3\right\}}^{**}$ , $Y_{\left\{v_1,v_2,v_3\right\}}$ , $Y_{\left\{v_2,v_3\right\}}$ , $Y_{\left\{v_3\right\}}$ , with the same order. For each $i\in \left\{1,\cdots ,m\right\}$ , put $\lceil \frac{\left|S_i\right|}{2}\rceil$ vertices of $S_i$ into V₂ and $\lfloor \frac{\left|S_i\right|}{2}\rfloor$ vertices of $S_i$ into V₁ if i is odd; and put $\lceil \frac{\left|S_i\right|}{2}\rceil$ vertices of $S_i$ into V₁ and $\lfloor \frac{\left|S_i\right|}{2}\rfloor$ vertices of $S_i$ into V₂ if i is even.

Finally, denote by $T_1,T_2,\cdots ,T_k$ the even sets of $Y_{\left\{v_2\right\}}$ , $Y_{\left\{v_1\right\}}$ , $Y_{\left\{v_1,v_3\right\}}^{**}$ , $Y_{\left\{v_1,v_2,v_3\right\}}$ , $Y_{\left\{v_2,v_3\right\}}$ , $Y_{\left\{v_3\right\}}$ . For each $i=1,\cdots ,k$ , put $\frac{\left|T_i\right|}{2}$ vertices of $T_i$ into V₁ and $\frac{\left|T_i\right|}{2}$ vertices of $T_i$ into V₂.

Now, we show that V₁ and V₂ form a weak external bisection of $G\left[X,Y\right]$ . Clearly, $\left|V_1\right|-\left|V_2\right|=0$ if m is odd, and $\left|V_1\right|-\left|V_2\right|=1$ if m is even. So $\left(V_1,V_2\right)$ is a bisection. Since $\left\{v_1,v_2\right\}\subseteq V_1$ and $Y_{\left\{v_1,v_2\right\}}\subseteq V_2$ , then $d_{ex}\left(v\right)-d_{in}\left(v\right)=2$ for each vertex $v\in Y_{\left\{v_1,v_2\right\}}$ . Moreover, $\left|d_{ex}\left(v\right)-d_{in}\left(v\right)\right|=1$ for each vertex $v\in Y_S$ if $S\subseteq \left\{v_1,v_2,v_3\right\}$ and $\left|S\right|=1$ or 3; and $d_{ex}\left(v\right)=d_{in}\left(v\right)$ for each vertex $v\in Y_S$ if $S\subseteq \left\{v_1,v_2,v_3\right\}$ , $S\ne \{v_1,v_2\}$ and $\left|S\right|=2$ . So, for each $v\in Y$ , $d_{ex}\left(v\right)\ge d_{in}\left(v\right)-1$ .

Let:

$\begin{array}{l}{S}_1=\left\{Y_{\left\{v_1\right\}},Y_{\left\{v_1,v_3\right\}}^{**},Y_{\left\{v_1,v_2,v_3\right\}}\right\},\\ S_2=\left\{Y_{\left\{v_1,v_2,v_3\right\}},Y_{\left\{v_2,v_3\right\}}\right\},\\ S_3=\left\{Y_{\left\{v_1,v_3\right\}}^{**},Y_{\left\{v_1,v_2,v_3\right\}},Y_{\left\{v_2,v_3\right\}},Y_{\left\{v_3\right\}}\right\}.\end{array}$

Let ${{\mathcal{S}}^{\prime }}_i=\left\{S_1,S_2,\cdots ,S_m\right\}\cap {\mathcal{S}}_i$ , for each $i=1,2,3$ . Note that $S_1,S_2,\cdots ,S_m$ are the odd sets of $Y_{\left\{v_2\right\}}$ , $Y_{\left\{v_1\right\}}$ , $Y_{\left\{v_1,v_3\right\}}^{**}$ , $Y_{\left\{v_1,v_2,v_3\right\}}$ , $Y_{\left\{v_2,v_3\right\}}$ , $Y_{\left\{v_3\right\}}$ , with the same order. Then, each ${{\mathcal{S}}^{\prime }}_i$ contains several continuous set of $S_1,S_2,\cdots ,S_m$ . Let ${\mathcal{T}}_i=\left\{T_1,T_2,\cdots ,T_k\right\}\cap {\mathcal{S}}_i$ , for each $i=1,2,3$ . We have:

$\begin{array}{l}{d}_{ex}\left(v_1\right)=\left|Y_{\left\{v_1,v_2\right\}}\right|+{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_1\\ i\text{isodd}\end{array}}{\sum }\lceil \frac{\left|S_i\right|}{2}\rceil }+{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_1\\ i\text{iseven}\end{array}}{\sum }\lfloor \frac{\left|S_i\right|}{2}\rfloor }+{\displaystyle \underset{T_i\subseteq {\mathcal{T}}_1}{\sum }\frac{\left|T_i\right|}{2}};\\ d_{in}\left(v_1\right)=\left|Y_{\left\{v_1,v_3\right\}}^{*}\right|+{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_1\\ i\text{isodd}\end{array}}{\sum }\lfloor \frac{\left|S_i\right|}{2}\rfloor }+{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_1\\ i\text{iseven}\end{array}}{\sum }\lceil \frac{\left|S_i\right|}{2}\rceil }+{\displaystyle \underset{T_i\subseteq {\mathcal{T}}_1}{\sum }\frac{\left|T_i\right|}{2}}.\end{array}$

Since ${{\mathcal{S}}^{\prime }}_1$ contains continuous set of $S_1,S_2,\cdots ,S_m$ , then we see that $\left|d_{ex}\left(v_1\right)-d_{in}\left(v_1\right)\right|=f\left({{\mathcal{S}}^{\prime }}_1\right)$ , where $f\left({{\mathcal{S}}^{\prime }}_1\right)$ is defined as (1). It is easy to see that:

$\begin{array}{l}{d}_{ex}\left(v_2\right)=\left|Y_{\left\{v_1,v_2\right\}}\right|+\lceil \frac{\left|Y_{\left\{v_2\right\}}\right|}{2}\rceil +{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_2\\ i\text{isodd}\end{array}}{\sum }\lceil \frac{\left|S_i\right|}{2}\rceil }+{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_2\\ i\text{iseven}\end{array}}{\sum }\lfloor \frac{\left|S_i\right|}{2}\rfloor }+{\displaystyle \underset{T_i\subseteq {\mathcal{T}}_2}{\sum }\frac{\left|T_i\right|}{2}};\\ d_{in}\left(v_2\right)=\lfloor \frac{\left|Y_{\left\{v_2\right\}}\right|}{2}\rfloor +{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_2\\ i\text{isodd}\end{array}}{\sum }\lfloor \frac{\left|S_i\right|}{2}\rfloor }+{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_2\\ i\text{iseven}\end{array}}{\sum }\lceil \frac{\left|S_i\right|}{2}\rceil }+{\displaystyle \underset{T_i\subseteq {\mathcal{T}}_2}{\sum }\frac{\left|T_i\right|}{2}}.\end{array}$

Clearly, if $\left|Y_{\left\{v_2\right\}}\right|$ is odd, then $S_1=Y_{\left\{v_2\right\}}$ . Thus, we have $d_{ex}\left(v_2\right)-d_{in}\left(v_2\right)\ge \left|Y_{\left\{v_1,v_2\right\}}\right|+f\left(Y_{\left\{v_2\right\}}\right)-f\left({{\mathcal{S}}^{\prime }}_2\right)\ge -1$ . Similarly, we have:

$\begin{array}{l}{d}_{ex}\left(v_3\right)=\left|Y_{\left\{v_1,v_3\right\}}^{*}\right|+{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_3\\ i\text{isodd}\end{array}}{\sum }\lfloor \frac{\left|S_i\right|}{2}\rfloor }+{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_3\\ i\text{iseven}\end{array}}{\sum }\lceil \frac{\left|S_i\right|}{2}\rceil }+{\displaystyle \underset{T_i\subseteq {\mathcal{T}}_3}{\sum }\frac{\left|T_i\right|}{2}};\\ d_{in}\left(v_3\right)={\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_3\\ i\text{isodd}\end{array}}{\sum }\lceil \frac{\left|S_i\right|}{2}\rceil }+{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_3\\ i\text{iseven}\end{array}}{\sum }\lfloor \frac{\left|S_i\right|}{2}\rfloor }+{\displaystyle \underset{T_i\subseteq {\mathcal{T}}_3}{\sum }\frac{\left|T_i\right|}{2}}.\end{array}$

So, we have $\left|d_{ex}\left(v_3\right)-d_{in}\left(v_3\right)\right|\ge \left|Y_{\left\{v_1,v_3\right\}}^{*}\right|-f\left({{\mathcal{S}}^{\prime }}_2\right)$ . Then, for each $v_i\in X$ , $d_{ex}\left(v_i\right)\ge d_{in}\left(v_i\right)-1$ . Thus, $\left(V_1,V_2\right)$ is a weak external bisection of $G\left[X,Y\right]$ .n

Proof of Theorem 1.2. Let $V\left(G_{n,m}\right)=\left\{u_i|i=1,\cdots ,n\right\}\cup \left\{v_i|i=1,\cdots ,n\right\}\underset{i=1}{\overset{n}{\cup }}\left\{u_{ij}|j=1,\cdots ,m\right\}$ . We give a weak external bisection $\left(V_1,V_2\right)$ of $V\left(G_{n,m}\right)$ by two steps.

First, let $\left\{v_i|i\in \left\{1,2,\cdots ,n\right\}\text{and}i\text{isodd}\right\}\subset V_2$ and $\left\{v_i|i\in \left\{1,2,\cdots ,n\right\}\text{and}i\text{iseven}\right\}\subset V_1$ . Let $\left\{u_i|i\in \left\{1,2,\cdots ,n\right\}\text{and}i\text{isodd}\right\}\subset V_1$ and $\left\{u_i|\left\{i\in 1,2,\cdots ,n\right\}\text{and}i\text{iseven}\right\}\subset V_2$ .

Then, we partition the set $\underset{i=1}{\overset{n}{\cup }}\left\{u_{ij}|j=1,2,\cdots ,m\right\}$ . The partition of $\underset{i=1}{\overset{n}{\cup }}\left\{u_{ij}|j=1,2,\cdots ,m\right\}$ is determined by $\underset{i=1}{\overset{n}{\cup }}\left\{u_i\right\}$ . For a given k, if $u_k\in V_1$ , let $\left\{u_{kj}|j\in \left\{1,2,\cdots ,m\right\}\text{and}j\text{isodd}\right\}\subset V_2$ and $\left\{u_{kj}|j\in \left\{1,2,\cdots ,m\right\}\text{and}j\text{iseven}\right\}\subset V_1$ ; if $u_k\in V_2$ , let $\left\{u_{kj}|j\in \left\{1,2,\dots ,m\right\}\text{and}j\text{isodd}\right\}\subset V_1$ and $\left\{u_{kj}|j\in \left\{1,2,\cdots ,m\right\}\text{and}j\text{iseven}\right\}\subset V_2$ .

Now, we show that V₁ and V₂ form a weak external bisection of $G_{n,m}$ . Clearly, $\left|V_1\right|-\left|V_2\right|=1$ if both n and m are odd. Otherwise, $\left|V_1\right|-\left|V_2\right|=0$ . So, $\left(V_1,V_2\right)$ is a bisection. If n is even, then $d_{ex}\left(v\right)-d_{in}\left(v\right)=3$ for each $v\in \underset{i=1}{\overset{n}{\cup }}\left\{v_i\right\}$ . If n is odd, then $d_{ex}\left(v_1\right)-d_{in}\left(v_1\right)=1$ , $d_{ex}\left(v_n\right)-d_{in}\left(v_n\right)=1$ and $d_{ex}\left(v\right)-d_{in}\left(v\right)=3$ for each $v\in \underset{i=2}{\overset{n-1}{\cup }}\left\{v_i\right\}$ . So, in any case, $d_{ex}\left(v_i\right)\ge d_{in}\left(v_i\right)$ for $i=1,2,\cdots ,n$ .

If m is odd, then $d_{ex}\left(v\right)-d_{in}\left(v\right)=2$ for each $v\in \underset{i=1}{\overset{n}{\cup }}\left\{u_{i1},u_{im}\right\}$ , $d_{ex}\left(v\right)-d_{in}\left(v\right)=1$ for each $v\in \underset{i=1}{\overset{n}{\cup }}\left\{u_{ij}|j\in \left\{2,\cdots ,m-1\right\}\text{and}j\text{iseven}\right\}$ and $d_{ex}\left(v\right)-d_{in}\left(v\right)=3$ for each $v\in \underset{i=1}{\overset{n}{\cup }}\left\{u_{ij}|j\in \left\{2,\cdots ,m-1\right\}\text{and}j\text{isodd}\right\}$ . If m is even, then $d_{ex}\left(u_{i1}\right)-d_{in}\left(u_{i1}\right)=2$ , $d_{ex}\left(u_{im}\right)=d_{in}\left(u_{im}\right)$ , $d_{ex}\left(v\right)-d_{in}\left(v\right)=1$ for each $v\in \underset{i=1}{\overset{n}{\cup }}\left\{u_{ij}|j\in \left\{2,\cdots ,m-1\right\}\text{and}j\text{iseven}\right\}$ and $d_{ex}\left(v\right)-d_{in}\left(v\right)=3$ for each $v\in \underset{i=1}{\overset{n}{\cup }}\left\{u_{ij}|j\in \left\{2,\cdots ,m-1\right\}\text{and}j\text{isodd}\right\}$ . So, in any case, $d_{ex}\left(u_{ij}\right)\ge d_{in}\left(u_{ij}\right)$ for $i=1,2,\cdots ,n$ ; $j=1,2,\cdots ,m$ .

If both n and m are odd, then $d_{ex}\left(u_1\right)-d_{in}\left(u_1\right)=2$ , $d_{ex}\left(u_n\right)-d_{in}\left(u_n\right)=2$ and $d_{ex}\left(v\right)-d_{in}\left(v\right)=4$ for each $v\in \underset{i=2}{\overset{n-1}{\cup }}\left\{u_i\right\}$ . If n is odd and m is even, then $d_{ex}\left(u_1\right)-d_{in}\left(u_1\right)=1$ , $d_{ex}\left(u_n\right)-d_{in}\left(u_n\right)=1$ and $d_{ex}\left(v\right)-d_{in}\left(v\right)=3$ for each $v\in \underset{i=2}{\overset{n-1}{\cup }}\left\{u_i\right\}$ . If n is even and m is odd, then $d_{ex}\left(v\right)-d_{in}\left(v\right)=4$ for each $v\in \underset{i=1}{\overset{n}{\cup }}\left\{u_i\right\}$ . If both n and m are even, then $d_{ex}\left(v\right)-d_{in}\left(v\right)=3$ for each $v\in \underset{i=1}{\overset{n}{\cup }}\left\{u_i\right\}$ . So, in any case, $d_{ex}\left(u_i\right)\ge d_{in}\left(v_i\right)$ for $i=1,2,\cdots ,n$ . Thus, $\left(V_1,V_2\right)$ is a weak external bisection of $G_{n,m}$ .n

Proof of Theorem 1.3. We labeled the vertices of graph $K_m^{\left(n\right)}$ as in Figure 2. $V\left(K_m^{\left(n\right)}\right)=\left\{x_0\right\}\underset{i=1}{\overset{n}{\cup }}\left\{x_{i1},x_{i2},\cdots ,x_{i,m-1}\right\}$ . Let $\left\{x_0\right\}\subset V_1$ .

We consider the following two cases.

Case 1. m is odd.

Let $\underset{i=1}{\overset{n}{\cup }}\left\{x_{ij}|j\in \left\{1,2,\cdots ,m-1\right\}\text{and}j\text{iseven}\right\}\subset V_1$ and $\underset{i=1}{\overset{n}{\cup }}\left\{x_{ij}|j\in \left\{1,2,\cdots ,m-1\right\}\text{and}j\text{isodd}\right\}\subset V_2$ . Now $\left|V_1\right|-\left|V_2\right|=1$ . So $\left(V_1,V_2\right)$ is a bisection. $d_{ev}\left(x_0\right)-d_{in}\left(x_0\right)=1$ . For each $v\in \underset{i=1}{\overset{n}{\cup }}\left\{x_{ij}|j\in \left\{1,2,\cdots ,m-1\right\}\text{and}j\text{iseven}\right\}$ , $d_{ev}\left(v\right)=d_{in}\left(v\right)$ . For each $v\in \underset{i=1}{\overset{n}{\cup }}\left\{x_{ij}|j\in \left\{1,2,\cdots ,m-1\right\}\text{and}j\text{isodd}\right\}$ , $d_{ev}\left(v\right)-d_{in}\left(v\right)=2$ . Thus, $\left(V_1,V_2\right)$ is a weak external bisection of $K_m^{\left(n\right)}$ .

Case 2. m is even.

If i is odd, let $\underset{i=1}{\overset{n}{\cup }}\left\{x_{ij}|j\in \left\{1,2,\cdots ,m-1\right\}\text{and}j\text{isodd}\right\}\subset V_2$ and let $\underset{i=1}{\overset{n}{\cup }}\left\{x_{ij}|j\in \left\{1,2,\cdots ,m-1\right\}\text{and}j\text{iseven}\right\}\subset V_1$ . If i is even, let $\underset{i=1}{\overset{n}{\cup }}\left\{x_{ij}|j\in \left\{1,2,\cdots ,m-1\right\}\text{and}j\text{isodd}\right\}\subset V_1$ and let $\underset{i=1}{\overset{n}{\cup }}\left\{x_{ij}|j\in \left\{1,2,\cdots ,m-1\right\}\text{and}j\text{iseven}\right\}\subset V_2$ .

Now, we show that V₁ and V₂ form a weak external bisection of $K_m^{\left(n\right)}$ . Clearly, $\left|V_1\right|-\left|V_2\right|=0$ if n is odd and $\left|V_1\right|-\left|V_2\right|=1$ if n is even. So $\left(V_1,V_2\right)$ is a bisection. If i is odd, $d_{ev}\left(v\right)-d_{in}\left(v\right)=1$ for each $v\in \left\{x_{ij}|j\in \left\{1,\cdots ,m-1\right\}\text{and}j\text{isodd}\right\}$ ; and $d_{ev}\left(v\right)-d_{in}\left(v\right)=1$ for each $v\in \left\{x_{ij}|j\in \left\{1,\cdots ,m-1\right\}\text{and}j\text{iseven}\right\}$ . If i is even, then $d_{ev}\left(v\right)-d_{in}\left(v\right)=-1$ for each $v\in \left\{x_{ij}|j\in \left\{1,\cdots ,m-1\right\}\text{and}j\text{isodd}\right\}$ ; and $d_{ev}\left(v\right)-d_{in}\left(v\right)=3$ for each $v\in \left\{x_{ij}|j\in \left\{1,\cdots ,m-1\right\}\text{and}j\text{iseven}\right\}$ . If n is even, then $d_{ev}\left(x_0\right)=d_{in}\left(x_0\right)$ . If n is odd, then $d_{ev}\left(x_0\right)-d_{in}\left(x_0\right)=1$ . Thus, $\left(V_1,V_2\right)$ is a weak external bisection of $K_m^{\left(n\right)}$ .n

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Ban, A. and Linial, N. (2016) Internal Partitions of Regular Graphs. Journal of Graph Theory, 83, 5-18. https://doi.org/10.1002/jgt.21909
[2]	Bollobás, B., and Scott, A.D. (2002) Problems and Results on Judicious Partitions. Random Structures & Algorithms, 21, 414-430. https://doi.org/10.1002/rsa.10062
[3]	Esperet, L., Mazzuoccolo, G. and Tarsi, M. (2017) Flows and Bisections in Cubic Graphs. Journal of Graph Theory, 86, 149-158. https://doi.org/10.1002/jgt.22118
[4]	Zhou, X.H. (2009) Adjacent Vertex Distinguishing Incidence Chromatic Number of Crown Graph Gn,m. Journal of Shandong University of Technology (Natural Science Edition), 23, 40-43.
[5]	Ji, Y.L., Ma, J., Yan, J. and Yu, X.X. (2019) On Problems about Judicious Bipartitions of Graphs. Journal of Combinatorial Theory, Series B, 139, 230-250. https://doi.org/10.1016/j.jctb.2019.03.001