Article in volume
Authors:
Title:
On distance magic labelings of Hamming graphs and folded hypercubes
PDFSource:
Discussiones Mathematicae Graph Theory 44(1) (2024) 17-33
Received: 2021-06-01 , Revised: 2021-09-01 , Accepted: 2021-09-01 , Available online: 2021-09-13 , https://doi.org/10.7151/dmgt.2430
Abstract:
Let $Γ=(V,E)$ be a graph of order $n$. A distance magic labeling of $Γ$
is a bijection $\ell \colon V \to \{1,2, \ldots, n\}$ for which there exists a
positive integer $k$ such that $\sum_{x \in N(u)} \ell(x) = k$ for all vertices
$u \in 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 $\mathrm{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 $\mathrm{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
References:
- 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 - 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 - 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 - 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 - S. Cichacz, Distance magic graphs $G × C_n$, Discrete Appl. Math. 177 (2014) 80–87.
https://doi.org/10.1016/j.dam.2014.05.044 - 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 - 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 - 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 - D. Froncek, A note on incomplete regular torunaments with handicap two of order $n \equiv 8\pmod{16}$, Opuscula Math. 37 (2017) 557–566.
https://doi.org/10.7494/OpMath.2017.37.4.557 - 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 - 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 - 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 - R. Hill, A First Course in Coding Theory (Oxford University Press, Oxford, 1993).
- S. Lang, Algebra, in: Grad. Texts in Math. 211 (Springer-Verlag, New York, 2002).
https://doi.org/10.1007/978-1-4613-0041-0 - Š. 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 - 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.
- P. Savický, Examples of distance magic labelings of the $6$-dimensional hypercube.
arXiv: 2102.08212 - 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
Close