Magic labeling in graphs: Bounds, complexity, and an application to a variant of TSP

Let G be an undirected graph with n vertices and m edges. A natural number λ is said to be a magic labeling, positive magic labeling , and fractional positive magic labeling , if the edges can be labeled with nonnegative integers, naturals, and rationale ≥1, respectively, so that for each vertex the sum of the labels of incident edges is λ. G is said to be 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 λˆ * , λˆ * , and δ, respectively, we prove that λˆ * ≤ min {[ n /2]δ, 2 m , 2λˆ * ). The bound 2 m 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{ nm + n 2 &log n square;, nm log(( n/m )&log n square; + 2)}), and λˆ * , as well as a 2‐approximates solution to λˆ * 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 [ n /2]δ = 2λˆ * = 2λˆ * . 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. © 1996 John Wiley & Sons, Inc.