Magic labeling in graphs

Bounds, complexity, and an application to a variant of TSP

Bahman Kalantari, G. B. Khosrovshahi

Research output: Contribution to journalArticle

4 Citations (Scopus)

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 λ̂(Black star), λ̂*, and δ, respectively, we prove that λ̂(Black star) ≤ 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{nm + n2√log n, nm log((n/m)√log n + 2)}), and λ̂*, as well as a 2-approximates solution to λ̂(Black star) 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λ̂(Black star) = 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.

Original languageEnglish (US)
Pages (from-to)211-219
Number of pages9
JournalNetworks
Volume28
Issue number4
DOIs
StatePublished - Jan 1 1996

Fingerprint

Labeling
Stars
Labels
Testing

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

@article{eaa225642dc74a138589e65472e4d4a5,
title = "Magic labeling in graphs: Bounds, complexity, and an application to a variant of TSP",
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 λ̂(Black star), λ̂*, and δ, respectively, we prove that λ̂(Black star) ≤ 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{nm + n2√log n, nm log((n/m)√log n + 2)}), and λ̂*, as well as a 2-approximates solution to λ̂(Black star) 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λ̂(Black star) = 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.",
author = "Bahman Kalantari and Khosrovshahi, {G. B.}",
year = "1996",
month = "1",
day = "1",
doi = "10.1002/(SICI)1097-0037(199612)28:4<211::AID-NET5>3.0.CO;2-O",
language = "English (US)",
volume = "28",
pages = "211--219",
journal = "Networks",
issn = "0028-3045",
publisher = "Wiley-Liss Inc.",
number = "4",

}

Magic labeling in graphs : Bounds, complexity, and an application to a variant of TSP. / Kalantari, Bahman; Khosrovshahi, G. B.

In: Networks, Vol. 28, No. 4, 01.01.1996, p. 211-219.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Magic labeling in graphs

T2 - Bounds, complexity, and an application to a variant of TSP

AU - Kalantari, Bahman

AU - Khosrovshahi, G. B.

PY - 1996/1/1

Y1 - 1996/1/1

N2 - 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 λ̂(Black star), λ̂*, and δ, respectively, we prove that λ̂(Black star) ≤ 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{nm + n2√log n, nm log((n/m)√log n + 2)}), and λ̂*, as well as a 2-approximates solution to λ̂(Black star) 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λ̂(Black star) = 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.

AB - 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 λ̂(Black star), λ̂*, and δ, respectively, we prove that λ̂(Black star) ≤ 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{nm + n2√log n, nm log((n/m)√log n + 2)}), and λ̂*, as well as a 2-approximates solution to λ̂(Black star) 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λ̂(Black star) = 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.

UR - http://www.scopus.com/inward/record.url?scp=0038879425&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0038879425&partnerID=8YFLogxK

U2 - 10.1002/(SICI)1097-0037(199612)28:4<211::AID-NET5>3.0.CO;2-O

DO - 10.1002/(SICI)1097-0037(199612)28:4<211::AID-NET5>3.0.CO;2-O

M3 - Article

VL - 28

SP - 211

EP - 219

JO - Networks

JF - Networks

SN - 0028-3045

IS - 4

ER -