Magic graphs, a characterization. (English) Zbl 0657.05065

Jeurissen, R. H.

Eur. J. Comb. 9, No. 4, 363-368 (1988).

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

MSC:

05C99

Graph theory

Keywords:

handle; pseudo-magic; index; magic graph; positive magic; balanced bipartite graphs; cross-bridge

References:

[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