“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 120 |
|
||||
| Abstract: | |||||
|
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 rationals ≥ 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 ⎤δ, 2m, 2∧λ* }. 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+ n2√{logn}, nm log((n/m) √{logn} + 2) }), and ∧λ*, as well as a 2-approximates solution to ∧λ* can be computed in O(T(n,m) logn) 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.
Download TeX format |
|||||
| back to top | |||||
