A Hamiltonian circle is a circle that contains all the vertices of the graph. The problem of the existence of Hamiltonian circle has been a highly significant problem in graph theory, because it’s NP-hard. Researchers have tried to give some tight sufficient conditions to prove the existence of Hamiltonian circles, among which the minimum degree condition (Dirac condition), the minimum degree sum condition (Ore condition) and the Fan-type condition are three classical results.

Inspired by the problem of Turán-type extremal graphs, we hope to give a sufficient condition for the existence of Hamiltonian circles in balanced multipartite graphs in terms of the number of edges, i.e., there must be a Hamiltonian circle for as many edges as there are at least in a balanced multipartite graph. Complete balanced multipartite graphs have a lot of great structural properties, such as having Hamiltonian circles, which can be used as a structural basis for interconnection networks. Connections are often broken in networks, so the fault tolerance of edges can be an important indicator of the stability of a network. The paper can provide an important theoretical support for determining the fault tolerance of complete multipartite graphs with Hamiltonian circles from the perspective of the number of edges, making it the basis of network structure.

Let $G_{k,n}$ be the complete $n$-balanced $k$-partite graph, whose vertex set can be partitioned into $k$ parts, each has $n$ vertices. Our main result is the following theorem.

All graphs considered in this paper are simple, finite, loop-free and undirected. For a graph $G$, let $V(G),E(G)$ denote the vertex set and edge set of $G$, respectively. For a vertex $u\in V(G)$, let $N_{G}(u)$ be the set of adjacent vertices to $u$ in $G$ and $d_{G}(u)=|N_{G}(u)|$.

Let $G_{n_{1},\cdots,n_{k}}=(V(G_{n_{1},\cdots,n_{k}}),E(G_{n_{1},\cdots,n_{k}}))$ be a $k$-partite graph with order $n_{1}+n_{2}+\cdots+n_{k}$, where the vertex set $V(G_{n_{1},\cdots,n_{k}})$ can be divided into $k$ parts $V_{1},V_{2},\cdots,V_{k}$ with $|V_{i}|=n_{i}$ for $1\leq i\leq k$ and the edge set $E(G_{n_{1},\cdots,n_{k}})$ contains edges with no two vertices from one part. If the edge set $E(G_{n_{1},\cdots,n_{k}})$ contains all edges with no two vertices from one part, then we call $G_{n_{1},\cdots,n_{k}}$ the complete $k$-partite graph with order $n_{1}+n_{2}+\cdots+n_{k}$, and denote the graph by $CG_{n_{1},\cdots,n_{k}}$. If $n_{1}=\cdots=n_{k}$, for simplicity, we write $G_{k,n}$ and $CG_{k,n}$ instead, and call $G_{k,n}$ an $n$-balanced $k$-partite graph. Let $\overline{G_{n_{1},\cdots,n_{k}}}$ be the $k$-partite graph with the vertex set $V(G_{n_{1},\cdots,n_{k}})$ and the edge set $E(CG_{n_{1},\cdots,n_{k}})\setminus E(G_{n_{1},\cdots,n_{k}})$. Clearly $|E(G_{n_{1},\cdots,n_{k}})|+|E(\overline{G_{n_{1},\cdots,n_{k}}})|=|E(CG_{n_{1},\cdots,n_{k}})|$ and $|E(G_{k,n})|+|E(\overline{G_{k,n}})|=|E(CG_{k,n})|$. Given a vertex $u\in V(G_{k,n})$, clearly $d_{\overline{G_{k,n}}}(u)+d_{G_{k,n}}(u)=(k-1)n$. Let $\delta(G_{k,n})$ be the smallest degree among all vertices and $\sigma(G_{k,n})$ be the smallest degree sum of two nonadjacent vertices from different parts.

The following results will be used in our proof.

Suppose that $G_{k,n}=(V(G_{k,n}),E(G_{k,n}))$ is an $n$-balanced $k$-partite graph with $k$ parts $V_{1}$, $V_{2}$, $\cdots,$ $V_{k}$ and $|E(G_{k,n})|\geq\binom{k}{2}n^{2}-(k-1)n+2$, where $k\geq 2$, $n\geq 1$ except $k=2$, $n=1$. Recall that $E(\overline{G_{k,n}})=E(CG_{k,n})\setminus E(G_{k,n})$, we have

If $n=1$, then $|E(G_{k,1})|\geq\binom{k-1}{2}+2$, by Theorem 3, the result holds.

Next we prove the case when $k\geq 3,n\geq 3$ by induction on $n$. We assume

Otherwise, by Theorem 6, $G_{k,n}$ is Hamiltonian. Without loss of generality, we let $u_{1}\in V_{1}$ and $v\in V_{2}$ be two nonadjacent vertices such that

and

Furthermore, since $d_{\overline{G_{k,n}}}(u)+d_{G_{k,n}}(u)=(k-1)n$ for any vertex $u\in V(G_{k,n})$, we obtain:

and

Clearly $\delta(G_{k,n})\geq 2$ as $|E(G_{k,n})|\geq\binom{k}{2}n^{2}-(k-1)n+2$. Therefore $d_{G_{k,n}}(u_{1})\geq 2$. We distinguish the following two cases:

Let $G=G_{k,n}-\{u_{1},v\}$. We claim that

Otherwise, there exists a vertex $u\in V(G)$ such that $d_{G}(u)\leq(k-2)n-1$. If $u\in V_{1}$ or $V_{2}$, then

If $u\in V_{i}$, $3\leq i\leq k$, then

Combining with (7), we obtain that

If $k$ is odd, then

if $k$ is even, then

It is a contradiction.

If $N_{G_{k,n}}(u_{1})\cap V_{2}\neq\emptyset$, without loss of generality, we let $u_{2}\in V_{2}$ and $u_{3}\in V_{3}$ be two adjacent vertices to $u_{1}$. By 9, we can greedily find a path $P=u_{2}-u_{1}-u_{3}-\cdots-u_{k}$ of length $k$, where $u_{i}\in V_{i}$ for $i=2,\cdots,k$. Otherwise there exists $3\leq i\leq k-1$ such that $N_{G}(u_{i})\cap V_{i+1}=\emptyset$. Then $d_{G}(u_{i})\leq 2(n-1)+(k-4)n=(k-2)n-2$, a contradiction. If $N_{G_{k,n}}(u_{1})\cap V_{2}=\emptyset$, without loss of generality, we let $u_{3}\in V_{3}$ and $u_{4}\in V_{4}$ be two adjacent vertices to $u_{1}$. Similarly, by 9, we can greedily find a path $P=u_{3}-u_{1}-u_{4}-\cdots-u_{k}-u_{2}$, where $u_{i}\in V_{i}$ for $i=2,\cdots,k$ and $u_{2}\neq v$. Otherwise there exists $4\leq i\leq k-1$ such that $N_{G}(u_{i})\cap V_{i+1}=\emptyset$ or $N_{G}(u_{k})\cap V_{2}\setminus\{v\}=\emptyset$. Then $d_{G}(u_{i})\leq(k-2)n-1$, a contradiction. Clearly the path $P$ contains one and only one vertex from every part.

Suppose $P=u_{2}-u_{1}-u_{3}-u_{4}-\cdots-u_{k}$ (The case when $P=u_{3}-u_{1}-u_{4}-\cdots-u_{k}-u_{2}$ is similar). By (1) and (8), we obtain that $\overline{G_{k,n}-V(P)}$ is a $(n-1)-$balanced $k$-partite graph with at most $\left(\frac{k}{2}-\frac{1}{k+1}\right)n-2$ edges if $k$ is odd and at most $\left(\frac{k}{2}-\frac{2}{k+2}\right)n-2$ edges if $k$ is even. It is not difficult to check that

as $k\geq 3$, $n\geq 3$. It follows that $G_{k,n}-V(P)$ contains at least $\binom{k}{2}(n-1)^{2}-(k-1)(n-1)+2$ edges. By inductive hypothesis, $G_{k,n}-V(P)$ contains a Hamilton cycle, denoted by

If $k(n-1)$ is odd, we construct a matching $M$ of size $\frac{k(n-1)-1}{2}$ from the edges of $C$ with $v\notin V(M)$:

If $k(n-1)$ is even, we construct a matching $M$ of size $\frac{k(n-1)-2}{2}$ from the edges of $C$ with $v\notin V(M)$:

We have the following claim.

By Claim 9, we obtain a Hamilton cycle of $G_{k,n}$ from $P$ and $C$. Without loss of generality, we can assume $\{v_{1},v_{2}\}$ of $M$ satisfying: $\{u_{2},v_{1}\},\{u_{k},v_{2}\}\ \in E(G_{k,n})$. Obviously $v_{1}-u_{2}-P-u_{k}-v_{2}-C-v_{1}$ is a Hamilton cycle of $G_{k,n}$.

In this case we have $d_{G_{k,n}}(u_{1})\leq n$. If $k=3$ and $n=3$, then it is easy to check that $G_{3,3}$ contains a Hamilton cycle. Suppose that $k\geq 3$, $n\geq 3$ except $k=3$ and $n=3$. We have the following claim.

Suppose that $N_{G_{k,n}}(u_{1})\subseteq V_{2}$. Let $u_{2},u_{2}^{\prime}\in N_{G_{k,n}}(u_{1})\subseteq V_{2}$. We claim that there exist two disjoint paths of length $k$:

where $u_{i}\neq u_{i}^{\prime}\in V_{i}$ for $i=1,2,\cdots,k$. First, we can greedily construct $P_{1}$. By Claim 10, $\delta(G_{k,n}-u_{1})\geq(k-2)n+1$, we obtain that $N_{G_{k,n}-u_{1}}(u_{i})\cap V_{i+1}\neq\emptyset$ for $2\leq i\leq k-1$. Next, we can also greedily construct $P_{2}$. Otherwise, there exists $u_{i}^{\prime}\in V_{i}$ such that $N_{G_{k,n}-u_{1}}(u_{i}^{\prime})\cap V_{i+1}\setminus\{u_{i}\}=\emptyset$ for $2\leq i\leq k-1$ or $N_{G_{k,n}-u_{1}}(u_{k}^{\prime})\cap V_{1}\setminus\{u_{1}\}=\emptyset$. It follows that $d_{G_{k,n}-u_{1}}(u_{i}^{\prime})\leq kn-1-n-(n-1)=(k-2)n$, a contradiction.

Suppose that $N_{G_{k,n}}(u_{1})\subseteq V_{i}$ for $3\leq i\leq k$. Without loss of generality, we let $u_{3},u_{3}^{\prime}\in N_{G_{k,n}}(u_{1})\subseteq V_{3}$. We claim that there exist two disjoint paths of length $k$:

where $u_{i}\neq u_{i}^{\prime}\in V_{i}$ for $i=1,2,\cdots,k$. Especially, if $k=3$, we can let $u_{2}\neq v$. The explanation is similar to the case when $N_{G_{k,n}}(u_{1})\subseteq V_{2}$.

Recall that $d_{G_{k,n}}(u_{1})\leq n$. Clearly $d_{\overline{G_{k,n}}}(u_{1})\geq(k-2)n$. By (1), we derive that

Therefore $G_{k,n}-V(P_{1})-V(P_{2})$ is a $(n-2)-$balanced $k$-partite graph with at least