Geodesic
On distance magic labelings of Hamming graphs and folded hypercubes
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 17-33 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Let Γ=(V,E) be a graph of order n. A distance magic labeling of Γ is a bijection 𝓁 : V →{1,2, . . . , n} for which there exists a positive integer k such that ∑_x ∈ N(u)𝓁(x) = k for all vertices u ∈ V, where N(u) is the neighborhood of u. A graph is said to be distance magic if it admits a distance magic labeling. The Hamming graph H(D,q), where D, q are positive integers, is the graph whose vertex set consists of all words of length D over an alphabet of size q in which two vertices are adjacent whenever the corresponding words differ in precisely one position. The well-known hypercubes are precisely the Hamming graphs with q = 2. Distance magic hypercubes were classified in two papers from 2013 and 2016. In this paper we consider all Hamming graphs. We provide a sufficient condition for a Hamming graph to be distance magic and as a corollary provide an infinite number of pairs (D, q) for which the corresponding Hamming graph H(D,q) is distance magic. A folded hypercube is a graph obtained from a hypercube by identifying pairs of vertices at maximal distance. We classify distance magic folded hypercubes by showing that the dimension-D folded hypercube is distance magic if and only if D is divisible by 4.
Keywords: distance magic labeling, distance magic graph, Hamming graph, folded hypercube 
@article{DMGT_2024_44_1_a1,
     author = {Miklavi\v{c}, \v{S}tefko and \v{S}parl, Primoz},
     title = {On distance magic labelings of {Hamming} graphs and folded hypercubes},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {17--33},
     year = {2024},
     volume = {44},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a1/}
}
TY  - JOUR
AU  - Miklavič, Štefko
AU  - Šparl, Primoz
TI  - On distance magic labelings of Hamming graphs and folded hypercubes
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 17
EP  - 33
VL  - 44
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a1/
LA  - en
ID  - DMGT_2024_44_1_a1
ER  - 
%0 Journal Article
%A Miklavič, Štefko
%A Šparl, Primoz
%T On distance magic labelings of Hamming graphs and folded hypercubes
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 17-33
%V 44
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a1/
%G en
%F DMGT_2024_44_1_a1
Miklavič, Štefko; Šparl, Primoz. On distance magic labelings of Hamming graphs and folded hypercubes. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 17-33. http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a1/

[1] S. Arumugam, D. Froncek and N. Kamatchi, Distance magic graphs –- A survey, J. Indones. Math. Soc., Special Edition (2011) 11–26. https://doi.org/10.22342/jims.0.0.15.11-26

[2] S. Arumugam, N. Kamatchi and G.R. Vijayakumar, On the uniqueness of D-vertex magic constant, Discuss. Math. Graph Theory 34 (2014) 279–286. https://doi.org/10.7151/dmgt.1728

[3] D. Bini, G.M. Del Corso, G. Manzini and L. Margara, Inversion of circulant matrices over \mathbb{Z}m, Math. Comp. 70 (2001) 1169–1182. https://doi.org/10.1090/S0025-5718-00-01235-7

[4] A.E. Brouwer, A.M. Cohen and A. Neumaier, Distance-Regular Graphs (Springer-Verlag, Berlin, 1989). https://doi.org/10.1007/978-3-642-74341-2

[5] S. Cichacz, Distance magic graphs G × Cn, Discrete Appl. Math. 177 (2014) 80–87. https://doi.org/10.1016/j.dam.2014.05.044

[6] S. Cichacz and D. Froncek, Distance magic circulant graphs, Discrete Math. 339 (2016) 84–94. https://doi.org/10.1016/j.disc.2015.07.002

[7] S. Cichacz, D. Froncek, E. Krop and C. Raridan, Distance magic Cartesian products of graphs, Discuss. Math. Graph Theory 36 (2016) 299–308. https://doi.org/10.7151/dmgt.1852

[8] S. Cichacz and A. Gőrlich, Constant sum partition of sets of integers and distance magic graphs, Discuss. Math. Graph Theory 38 (2018) 97–106. https://doi.org/10.7151/dmgt.1991

[9] D. Froncek, A note on incomplete regular torunaments with handicap two of order n ≡ 8 (mod 16), Opuscula Math. 37 (2017) 557–566. https://doi.org/10.7494/OpMath.2017.37.4.557

[10] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin.} (2017), #DS6. http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6/versions

[11] A. Godinho, T. Singh and S. Arumugam, The distance magic index of a graph, Discuss. Math. Graph Theory 38 (2018) 135–142. https://doi.org/10.7151/dmgt.1998

[12] P. Gregor and P. Kovár, Distance magic labelings of hypercubes, Electron. Notes Discrete Math. 40 (2013) 145–149. https://doi.org/10.1016/j.endm.2013.05.027

[13] R. Hill, A First Course in Coding Theory (Oxford University Press, Oxford, 1993).

[14] S. Lang, Algebra, in: Grad. Texts in Math. 211 (Springer-Verlag, New York, 2002). https://doi.org/10.1007/978-1-4613-0041-0

[15] Š. Miklavič and P. Šparl, Classification of tetravalent distance magic circulant graphs, Discrete Math. 344 (2021) 112557. https://doi.org/10.1016/j.disc.2021.112557

[16] S.B. Rao, Sigma graphs –- A survey, in: Labelings of Discrete Structures and Applications, B.D. Acharya, S. Arumugam and A. Rosa (Ed(s)), (Narosa Publishing House, New Delhi 2008) 135–140.

[17] P. Savický, Examples of distance magic labelings of the 6-dimensional hypercube. arXiv: 2102.08212

[18] Y. Tian, L. Hou, B. Hou and S. Gao, D-magic labelings of the folded n-cube, Discrete Math. 344 (2021) 112520. https://doi.org/10.1016/j.disc.2021.112520