Magic graphs, a characterization
type: Item
instance of: scholarly article
title: Magic graphs, a characterization
zbMATH Open document ID: 0657.05065
DOI: 10.1016/S0195-6698(88)80066-0
author: R. H. Jeurissen
published in: European Journal of Combinatorics
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4073033
zbMATH Keywords: handle
zbMATH Keywords: pseudo-magic
zbMATH Keywords: index
zbMATH Keywords: magic graph
zbMATH Keywords: positive magic
zbMATH Keywords: balanced bipartite graphs
zbMATH Keywords: cross-bridge
reviewed by: Z. J. Liu
MaRDI profile type: Publication
cites work: Regularisable Graphs
cites work: Regularisable graphs I
cites work: Regularisable graphs, II
cites work: Some Common Properties for Regularizable Graphs, Edge-Critical Graphs and B-Graphs
cites work: Characterizations of regular magic graphs
cites work: Pseudo-magic graphs
cites work: Disconnected graphs with magic labelings
cites work: Magic Graphs
cites work: Supermagic Complete Graphs
description: scientific article; zbMATH DE number 4073033