Abstract: Let G be a graph and \begin{document}$ (V_1,V_2,\cdots ,V_k) $\end{document} be a k-partition of G. For \begin{document}$ 1\leqslant i \lt j\leqslant k $\end{document}, the ratio of \begin{document}$ (V_i, V_j) $\end{document}, denoted by \begin{document}$ R(V_i, V_j) $\end{document}, is \begin{document}$ e(V_i, V_j)/(|V_i||V_j|) $\end{document}, where \begin{document}$ e(V_i,V_j) $\end{document} is the number of crossing edges. The minimum k-ratio of G, denoted by \begin{document}$ R_k(G) $\end{document}, is the minimum \begin{document}$ \sum _{1\leqslant i \lt j\leqslant k}R(V_i,V_j) $\end{document} over all k-partitions \begin{document}$ (V_1,V_2,\cdots ,V_k) $\end{document} of G. Let \begin{document}$ R(G)=R_2(G) $\end{document}. The ratio cut problem, posed by Wei and Cheng, and independently by Leighton and Rao, is an extension of the min-cut problem and has important applications in CAD. It is easy to see that \begin{document}$ R_k(G) $\end{document} is closely related to the density d(G) of a graph G. In this paper, we mainly give some results on \begin{document}$ R_k(G) $\end{document} with respect to d(G). First, we show that \begin{document}$ R_k(G)\leqslant {k \atopwithdelims ()2}(1+o(1))d(G) $\end{document} for graphs G and \begin{document}$ R_k(G)\leqslant (k-1)(1+o(1))d(G) $\end{document} for sparse graphs G. Then, we give some upper and lower bounds on R(G). In particular, we show \begin{document}$ R(G)\leqslant 4/(n-3) $\end{document} for every planar graph G with \begin{document}$ n\geqslant 4 $\end{document} vertices. At last, we consider the random graph G(n, p) and show that R(G(n, p)) can be determined asymptotically almost surely if \begin{document}$ p\geqslant C\log n/n $\end{document} for some constant \begin{document}$ C \gt 0 $\end{document}.

Key words: Partition, Min-cut, Ratio cut, Probabilistic method, Random graph