Magic graphs, a characterization (Q1110540)

A graph \(G=(P,L)\) with loopless is called magic if there is a map s: \(L\to Z\) such that no two edges have same integer, and the sum of integers s(e) of all edges e incident with a point v is the same for all v in P; its value is called the index of s. A magic graph is called positive magic if all integers assigned to the edges are positive. A cross-bridge is a pair of edges connecting disjoint bipartite graphs \(G=(X,Y;E)\) and \(G'=(X',Y';E')\), one of the edges from X to Y', the other from X' to Y. It is shown in section 2 of the paper that a connected bipartite graph \(G=(X,Y;E)\) is positive magic if and only if G is balanced, \(| N(S)| >| S|\) for all \(S\subset X\), \(S\neq \phi\), X, and G does not consist of two disjoint balanced bipartite graphs connected by a cross-bridge. Using this result a necessary and sufficient condition for a non-bipartite graph to be positive magic is given in section 3. The characterization of magic graph is described. In the last section the smallest indices of positive magic graphs are discussed. It is shown that \(K_ n\quad (n\neq 4m,\quad n>5) \& K_{3.3}\) have smallest indices \((n- 1)(n^ 2-n+2)/4\) and 24 respectively. It seems that it is difficult to find the smallest positive magic index for a general graph.