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

✍ Scribed by Kalantari, B.; Khosrovshahi, G. B.

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 674 KB
• Volume: 28
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199612)28:4<211::aid-net5>3.0.co;2-o

✦ Synopsis

Let G be an undirected graph with n vertices and m edges. A natural number A is said to be a magic labeling, positive magic /abe/ing, and fractional positive magic /abe/ing, if the edges can be labeled with nonnegative intqers, naturals, and rationals 2 1 , respectively, so that for each vertex the sum of the labels of incident edges is A. G is said to be mgu/atizab/e 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 i', L, and 6, respectively, we prove that h' s min{rn/216,2m, 2i*}. The bound 2m is also derivable from a characten'zation of regularizable graphs stated by Pulleyblank, and regularizability for graphs with nonbipartiie components can be tested via the Boutjolly-Pulleyblank algorithm for testing 2-bicriticali in O(nm) time. We show that using the above bounds and maximum flow algorithms of Ahuja-Orlin-T 'an regularizability (or 2-bicriticality) can be tested in T(n,m) = O(min{nm + n2&, nm log((nlm) ?log n + 2)}), and k,,, as well as a 2-approximates solution to h' 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 rn/216 = 2h* = 2i ,. 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. 0 7996 John Wiky & Sons, Inc.