Magic and supermagic dense bipartite graphs

Jaroslav Ivanco

Discussiones Mathematicae Graph Theory (2007)

  • Volume: 27, Issue: 3, page 583-591
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Jaroslav Ivanco. "Magic and supermagic dense bipartite graphs." Discussiones Mathematicae Graph Theory 27.3 (2007): 583-591. <http://eudml.org/doc/270151>.

@article{JaroslavIvanco2007,
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.},
author = {Jaroslav Ivanco},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {magic graphs; supermagic graphs; bipartite graphs},
language = {eng},
number = {3},
pages = {583-591},
title = {Magic and supermagic dense bipartite graphs},
url = {http://eudml.org/doc/270151},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Jaroslav Ivanco
TI - Magic and supermagic dense bipartite graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 3
SP - 583
EP - 591
AB - 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.
LA - eng
KW - magic graphs; supermagic graphs; bipartite graphs
UR - http://eudml.org/doc/270151
ER -

References

top
  1. [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. Zbl1008.05119
  2. [2] M. Doob, Characterizations of regular magic graphs, J. Combin. Theory (B) 25 (1978) 94-104, doi: 10.1016/S0095-8956(78)80013-6. Zbl0384.05054
  3. [3] J.A. Gallian, A dynamic survey of graph labeling, Electronic J. Combinatorics #DS6 36 (2003). Zbl0953.05067
  4. [4] N. Hartsfield and G. Ringel, Pearls in Graph Theory (Academic Press, Inc., San Diego, 1990). Zbl0703.05001
  5. [5] J. Ivanco, On supermagic regular graphs, Mathematica Bohemica 125 (2000) 99-114. Zbl0963.05121
  6. [6] J. Ivanco, Z. Lastivková and A. Semanicová, On magic and supermagic line graphs, Mathematica Bohemica 129 (2004) 33-42. 
  7. [7] R.H. Jeurissen, Magic graphs, a characterization, Europ. J. Combin. 9 (1988) 363-368. Zbl0657.05065
  8. [8] S. Jezný and M. Trenkler, Characterization of magic graphs, Czechoslovak Math. J. 33 (1983) 435-438. Zbl0571.05030
  9. [9] J. Moon and L. Moser, On Hamiltonian bipartite graphs, Isr. J. Math. 1 (1963) 163-165, doi: 10.1007/BF02759704. Zbl0119.38806
  10. [10] J. Sedlácek, On magic graphs, Math. Slovaca 26 (1976) 329-335. Zbl0348.05114
  11. [11] J. Sedlácek, Problem 27, in: Theory of Graphs and Its Applications, Proc. Symp. Smolenice (Praha, 1963) 163-164. 
  12. [12] B.M. Stewart, Magic graphs, Canad. J. Math. 18 (1966) 1031-1059, doi: 10.4153/CJM-1966-104-7. Zbl0149.21401
  13. [13] B.M. Stewart, Supermagic complete graphs, Canad. J. Math. 19 (1967) 427-438, doi: 10.4153/CJM-1967-035-9. Zbl0162.27801

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.