Download PDF - Magic and supermagic dense bipartite graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Magic and supermagic dense bipartite graphs

Authors 1

Affiliations

  1. Institute of Mathematics, P.J. Šafárik University, Jesenná 5, SK-041 54 Košice, Slovak Republic

Abstract

A graph is called magic (supermagic) if it admits a labelling of the edges by pairwise different (and consecutive) positive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In the paper we prove that any balanced bipartite graph with minimum degree greater than |V(G)|/4 ≥ 2 is magic. A similar result is presented for supermagic regular bipartite graphs.

Keywords

ENG
magic graphs, supermagic graphs, bipartite graphs

Bibliography

  1. A. Czygrinow and H.A. Kierstead, 2-factors in dense bipartite graphs, Discrete Math. 257 (2002) 357-369, doi: 10.1016/S0012-365X(02)00435-1.
  2. M. Doob, Characterizations of regular magic graphs, J. Combin. Theory (B) 25 (1978) 94-104, doi: 10.1016/S0095-8956(78)80013-6.
  3. J.A. Gallian, A dynamic survey of graph labeling, Electronic J. Combinatorics #DS6 36 (2003).
  4. N. Hartsfield and G. Ringel, Pearls in Graph Theory (Academic Press, Inc., San Diego, 1990).
  5. J. Ivanco, On supermagic regular graphs, Mathematica Bohemica 125 (2000) 99-114.
  6. J. Ivanco, Z. Lastivková and A. Semanicová, On magic and supermagic line graphs, Mathematica Bohemica 129 (2004) 33-42.
  7. R.H. Jeurissen, Magic graphs, a characterization, Europ. J. Combin. 9 (1988) 363-368.
  8. S. Jezný and M. Trenkler, Characterization of magic graphs, Czechoslovak Math. J. 33 (1983) 435-438.
  9. J. Moon and L. Moser, On Hamiltonian bipartite graphs, Isr. J. Math. 1 (1963) 163-165, doi: 10.1007/BF02759704.
  10. J. Sedlácek, On magic graphs, Math. Slovaca 26 (1976) 329-335.
  11. J. Sedlácek, Problem 27, in: Theory of Graphs and Its Applications, Proc. Symp. Smolenice (Praha, 1963) 163-164.
  12. B.M. Stewart, Magic graphs, Canad. J. Math. 18 (1966) 1031-1059, doi: 10.4153/CJM-1966-104-7.
  13. B.M. Stewart, Supermagic complete graphs, Canad. J. Math. 19 (1967) 427-438, doi: 10.4153/CJM-1967-035-9.
Discussiones Mathematicae Graph Theory
2007/27/3
Export to PBN, Opens in new tab
Pages:
583-591
Main language of publication
English
Received
2006-01-31
Accepted
2006-11-30
Published
2007

DOI: 10.7151/dmgt.1384

Exact and natural sciences