Magic graphs, a characterization. (English) Zbl 0657.05065

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.
Reviewer: Zhenhong Liu


05C99 Graph theory
Full Text: DOI


[1] Berge, C., Regularisable graphs, Ann. Discr. Math., 3, 11-19 (1978) · Zbl 0383.05031
[2] Berge, C., Regularisable graphs I, Discr. Math., 23, 85-89 (1978) · Zbl 0392.05050
[3] Berge, C., Regularisable graphs II, Discr. Math., 23, 91-95 (1978) · Zbl 0392.05051
[4] Berge, C., Some common properties for regularisable graphs and B-graphs, Ann. discr. Math., 12, 31-44 (1982) · Zbl 0501.05056
[5] Doob, M., Characterizations of regular magic graphs, J. Comb. Theory Ser. B,, 25, 94-104 (1978) · Zbl 0384.05054
[6] Jeurissen, R. H., Pseudo-magic graphs, Discr. Math., 43, 207-214 (1983) · Zbl 0514.05054
[7] Jeurissen, R. H., Disconnected graphs with magic labelings, Discr. Math., 43, 47-53 (1983) · Zbl 0499.05053
[8] Stewart, B. M., Magic Graphs, Can. J. Math., 18, 1031-1059 (1966) · Zbl 0149.21401
[9] Stewart, B. M., Supermajic Complete Graphs, Can. J. Math., 19, 427-438 (1967) · Zbl 0162.27801
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.