“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 BourjollyPulleyblank algorithm for testing 2bicriticality in O(nm) time. We show that using the above bounds and maximum flow algorithms of AhujaOrlinTarjan regularizability (or 2bicriticality) can be tested in T(n,m)=O(min{n m+ n^{2}√{logn}, nm log((n/m) √{logn} + 2) }), and ∧λ_{*}, as well as a 2approximates 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 2approximate 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 