Distance Magic Cartesian Products of Graphs

Sylwia Cichacz; Dalibor Froncek; Elliot Krop; Christopher Raridan

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 2, page 299-308
  • ISSN: 2083-5892

Abstract

top
A distance magic labeling of a graph G = (V,E) with |V | = n is a bijection ℓ : V → {1, . . . , n} such that the weight of every vertex v, computed as the sum of the labels on the vertices in the open neighborhood of v, is a constant. In this paper, we show that hypercubes with dimension divisible by four are not distance magic. We also provide some positive results by proving necessary and sufficient conditions for the Cartesian product of certain complete multipartite graphs and the cycle on four vertices to be distance magic.

How to cite

top

Sylwia Cichacz, et al. "Distance Magic Cartesian Products of Graphs." Discussiones Mathematicae Graph Theory 36.2 (2016): 299-308. <http://eudml.org/doc/277122>.

@article{SylwiaCichacz2016,
abstract = {A distance magic labeling of a graph G = (V,E) with |V | = n is a bijection ℓ : V → \{1, . . . , n\} such that the weight of every vertex v, computed as the sum of the labels on the vertices in the open neighborhood of v, is a constant. In this paper, we show that hypercubes with dimension divisible by four are not distance magic. We also provide some positive results by proving necessary and sufficient conditions for the Cartesian product of certain complete multipartite graphs and the cycle on four vertices to be distance magic.},
author = {Sylwia Cichacz, Dalibor Froncek, Elliot Krop, Christopher Raridan},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {distance magic labeling; magic constant; sigma labeling; Cartesian product; hypercube; complete multipartite graph; cycle},
language = {eng},
number = {2},
pages = {299-308},
title = {Distance Magic Cartesian Products of Graphs},
url = {http://eudml.org/doc/277122},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Sylwia Cichacz
AU - Dalibor Froncek
AU - Elliot Krop
AU - Christopher Raridan
TI - Distance Magic Cartesian Products of Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 2
SP - 299
EP - 308
AB - A distance magic labeling of a graph G = (V,E) with |V | = n is a bijection ℓ : V → {1, . . . , n} such that the weight of every vertex v, computed as the sum of the labels on the vertices in the open neighborhood of v, is a constant. In this paper, we show that hypercubes with dimension divisible by four are not distance magic. We also provide some positive results by proving necessary and sufficient conditions for the Cartesian product of certain complete multipartite graphs and the cycle on four vertices to be distance magic.
LA - eng
KW - distance magic labeling; magic constant; sigma labeling; Cartesian product; hypercube; complete multipartite graph; cycle
UR - http://eudml.org/doc/277122
ER -

References

top
  1. [1] B.D. Acharya, S.B. Rao, T. Singh and V. Parameswaran, Neighborhood magic graphs, National Conference on Graph Theory, Combinatorics and Algorithms, 2004. 
  2. [2] M. Anholcer and S. Cichacz, Note on distance magic graphs G◦C4, Graphs Combin. 31 (2015) 1117-1124. doi:10.1007/s00373-014-1453-x[Crossref] 
  3. [3] M. Anholcer, S. Cichacz and I. Peterin, Spectra of graphs and closed distance magic labelings, preprint, 2014. 
  4. [4] M. Anholcer, S. Cichacz, I. Peterin and A. Tepeh, Distance magic labeling and two product graphs, Graphs Combin. 31 (2015) 1125-1136. doi:10.1007/s00373-014-1455-8[Crossref] 
  5. [5] S. Arumugam, D. Froncek and N. Kamatchi, Distance magic graphs-a survey, J. Indones. Math. Soc., Special Edition (2011) 11-26. Zbl1288.05216
  6. [6] S. Beena, On ∑ and ∑′ labelled graphs, Discrete Math. 309 (2009) 1783-1787. doi:10.1016/j.disc.2008.02.038[Crossref] 
  7. [7] S. Cichacz, Group distance magic graphs G × C4, Discrete Appl. Math. 177 (2014) 80-87. doi:10.1016/j.dam.2014.05.044[Crossref] 
  8. [8] S. Cichacz and A. Görlich, Constant sum partitions of sets of integers and distance magic graphs, preprint, 2013. 
  9. [9] R. Diestel, Graph Theory, Fourth Ed., (Vol. 173 of Graduate Texts in Mathematics, Springer, Heidelberg, 2010). doi:10.1007/978-3-642-14279-6[Crossref] 
  10. [10] D. Froncek, Handicap distance antimagic graphs and incomplete tournaments, AKCE Int. J. Graphs Comb. 10 (2013) 119-127. Zbl1301.05289
  11. [11] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 5 (2013) DS 6. Zbl0953.05067
  12. [12] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Second Ed. (CRC Press, Boca Raton, FL, 2011). Zbl1283.05001
  13. [13] T. Harmuth, Über magische Quadrate und ähnliche Zahlenfiguren, Arch. Math. Phys. 66 (1881) 286-313. 
  14. [14] T. Harmuth, Über magische Rechtecke mit ungeraden Seitenzahlen, Arch. Math. Phys. 66 (1881) 413-447. 
  15. [15] M.I. Jinnah, On ∑-labelled graphs, in: B.D. Acharya and S.M. Hedge (Eds.), Technical Proceedings of Group Discussion on Graph Labeling Problems (1999) 71-77. 
  16. [16] M. Miller, C. Rodger and R. Simanjuntak, Distance magic labelings of graphs, Australas. J. Combin. 28 (2003) 305-315.  Zbl1031.05117
  17. [17] S.B. Rao, Sigma graphs-a survey, in: B.D. Acharya, S. Arumugam and A. Rosa, (Eds.), Labelings of Discrete Structures and Applications (Narosa Publishing House, New Delhi, 2008) 135-140. Zbl1180.05107
  18. [18] S.B. Rao, T. Singh and V. Parameswaran, Some sigma labelled graphs I, in: S. Arumugam, B.D. Acharya and S.B. Rao, (Eds.), Graphs, Combinatorics, Algorithms and Applications (Narosa Publishing House, New Delhi, 2014) 125-133. 
  19. [19] M.A. Seoud, A.E.I. Abdel Maqsoud and Y.I. Aldiban, New classes of graphs with and without 1-vertex magic vertex labeling, Proc. Pakistan Acad. Sci. 46 (2009) 159-174. 
  20. [20] V. Vilfred, ∑-labelled Graphs and Circulant Ggraphs, PhD Thesis (University of Kerala, Trivandrum, India, 1994). 

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.