×

zbMATH — the first resource for mathematics

Distance magic Cartesian products of graphs. (English) Zbl 1338.05226
Summary: A distance magic labeling of a graph \(G = (V,E)\) with \(|V | = n\) is a bijection \(\ell: V \to \{1,\dots,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.

MSC:
05C76 Graph operations (line graphs, products, etc.)
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[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] 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 · Zbl 1321.05227
[3] M. Anholcer, S. Cichacz and I. Peterin, Spectra of graphs and closed distance magic labelings, preprint, 2014.
[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 · Zbl 1327.05296
[5] S. Arumugam, D. Froncek and N. Kamatchi, Distance magic graphs-a survey, J. Indones. Math. Soc., Special Edition (2011) 11-26. · Zbl 1288.05216
[6] S. Beena, On ∑ and ∑′ labelled graphs, Discrete Math. 309 (2009) 1783-1787. doi:10.1016/j.disc.2008.02.038 · Zbl 1188.05108
[7] S. Cichacz, Group distance magic graphs G × C4, Discrete Appl. Math. 177 (2014) 80-87. doi:10.1016/j.dam.2014.05.044 · Zbl 1297.05201
[8] S. Cichacz and A. Görlich, Constant sum partitions of sets of integers and distance magic graphs, preprint, 2013.
[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
[10] D. Froncek, Handicap distance antimagic graphs and incomplete tournaments, AKCE Int. J. Graphs Comb. 10 (2013) 119-127. · Zbl 1301.05289
[11] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 5 (2013) DS 6. · Zbl 0953.05067
[12] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Second Ed. (CRC Press, Boca Raton, FL, 2011). · Zbl 1283.05001
[13] T. Harmuth, Über magische Quadrate und ähnliche Zahlenfiguren, Arch. Math. Phys. 66 (1881) 286-313. · JFM 13.0145.02
[14] T. Harmuth, Über magische Rechtecke mit ungeraden Seitenzahlen, Arch. Math. Phys. 66 (1881) 413-447. · JFM 13.0146.01
[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] M. Miller, C. Rodger and R. Simanjuntak, Distance magic labelings of graphs, Australas. J. Combin. 28 (2003) 305-315. · Zbl 1031.05117
[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. · Zbl 1180.05107
[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] 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] V. Vilfred, ∑-labelled Graphs and Circulant Ggraphs, PhD Thesis (University of Kerala, Trivandrum, India, 1994).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.