Magic labelings of graphs (Q2761040)

The authors investigate such integer labelings \(w\) (called ``magic'') of edges of a graph \(G\), in which \(\sum_{v\in e}w(e)\) is a constant \(s\) independent of the vertex \(v\). They introduce basis graphs of type I and II. For the type I a unique, up to a constant factor, labeling exists with \(s>0\) and no \(0\) label. For the type II the same labeling exists but with \(s=0\). Basis graphs of both types are characterized. An algorithm reducing the problem of finding positive labelings to an integer programming problem is presented. A connection to vertex cycle covers is discussed.