“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 120
School of Mathematics
  Title:   Magic labeling in graphs: bounds complexity and an application to a variant of TSP
  Author(s): 
1.  B. Kalantari
2.  G. B. Khosrovshahi
  Status:   Published
  Journal: Networks
  Vol.:  28
  Year:  1996
  Pages:   211-219
  Supported by:  IPM
  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
scroll left or right