Change search
ReferencesLink to record
Permanent link

Direct link
SAT and IP Based Algorithms for Magic Labeling Including a Complete Search for Total Magic Labelings
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
(Formal Methods & Tools Group, Department of Computer Science, University of Twente, The Nnetherlands)
2015 (English)In: Journal of Discrete Algorithms, ISSN 1570-8667, E-ISSN 1570-8675, Vol. 31, 87-103 p.Article in journal (Refereed) Published
Abstract [en]

In this paper a labeling of a graph with n vertices and m   edges is a one-to-one mapping from the union of the set of vertices and edges onto the set {1,2,…,m+n}. Such a labeling is defined as magic, if one or both of the following two conditions is fulfilled: the sum of an edge label and the labels of its endpoint vertices is constant for all edges; the sum of a vertex label and the labels of its incident edges is constant for all vertices. If a graph has a labeling fulfilling both conditions, it is called a totally magic graph. We present effective IP and Sat based algorithms for the problem of finding a magic labeling for a given graph, and we extend these algorithms also to find all magic labelings for a given graph. We experimentally compare the resulted algorithms by applying it to random graphs. Finally, we demonstrate its performance by solving small cases of seven open problems within the theory of magic graphs. As main practical result we perform an exhaustive search showing that no totally magic graph with 11 vertices exists.

Place, publisher, year, edition, pages
2015. Vol. 31, 87-103 p.
Keyword [en]
Boolean satisfiability, Integer programming, Magic labeling
National Category
Discrete Mathematics
URN: urn:nbn:se:umu:diva-100105DOI: 10.1016/j.jda.2015.01.011ISI: 000358518400008OAI: diva2:790211
Available from: 2015-02-23 Created: 2015-02-23 Last updated: 2015-12-15Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Jäger, Gerold
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Journal of Discrete Algorithms
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 78 hits
ReferencesLink to record
Permanent link

Direct link