\documentclass[12pt]{article}
\usepackage{amsmath,amssymb,amsfonts}
\begin{document}
Let $G$ be an undirected graph with $n$ vertices and $m$ edges. A natural number $\lambda$ is said to be a {\it magic labeling, positive magic labeling}, and {\it fractional positive magic labeling}, if the edges can be labeled with nonnegative
integers, naturals, and rationals $\geq 1$, respectively, so that for each vertex the sum of the labels of incident edges is $\lambda$. $G$ is said to be {\it regularizable} if it has a positive magic labeling. Denoting the minimum positive magic labeling, the minimum fractional
positive magic labeling, and the maximum vertex degree by $\hat{\lambda}^*, \hat{\lambda}_*$, and $\delta$, respectively,
we prove that $\hat{\lambda}^* \leq \min \{\lceil n/2 \rceil \delta, 2m, 2\hat{\lambda}_* \}$. The bound $2m$ is also derivable from a characterization of regularizable graphs stated by Pulleyblank, and regularizability for graphs with nonbipartite components can be tested via the Bourjolly-Pulleyblank algorithm for testing 2-bicriticality in $O(nm)$ time. We show that using the above bounds and maximum flow algorithms of Ahuja-Orlin-Tarjan regularizability (or 2-bicriticality) can be tested in $T(n,m)=O(\min \{n m+ n\sqrt[2]{\log n}, nm \log ((n/m) \sqrt{\log n} + 2) \})$, and $\hat{\lambda}_*$, as well as a 2-approximates solution to $\hat{\lambda}^*$ can be computed in $O(T(n,m) \log n)$ time. For dense graphs, $T(n,m)$ can be improved using parallel maximum flow algorithms. We exhibit a family of graphs for which $\lceil n/2 \rceil \delta= 2\hat{\lambda}^* =2\hat{\lambda}_*$. Finally, given that the edges in $G$ have nonnegative weights satisfying the triangle inequality, using a capacitated magic labeling solution, we construct a 2-approximate algorithm for the problem of covering all the vertices with optimal set of disjoint even cycles, each covering at
least four vertices.
\end{document}