Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Open Access

On Distance Magic Labelings of Hamming Graphs and Folded Hypercubes

Accepted: 01 Sep 2021
Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English

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 ΣxN(u) ℓ(x) = k for all vertices uV, 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.

MSC 2010

[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-2610.22342/jims.0.0.15.11-26Search in Google Scholar

[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.172810.7151/dmgt.1728Search in Google Scholar

[3] D. Bini, G.M. Del Corso, G. Manzini and L. Margara, Inversion of circulant matrices overm, Math. Comp. 70 (2001) 1169–1182. https://doi.org/10.1090/S0025-5718-00-01235-710.1090/S0025-5718-00-01235-7Search in Google Scholar

[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-210.1007/978-3-642-74341-2Search in Google Scholar

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

[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.00210.1016/j.disc.2015.07.002Search in Google Scholar

[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.185210.7151/dmgt.1852Search in Google Scholar

[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.199110.7151/dmgt.1991Search in Google Scholar

[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.55710.7494/OpMath.2017.37.4.557Search in Google Scholar

[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/versions10.37236/27Search in Google Scholar

[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.199810.7151/dmgt.1998Search in Google Scholar

[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.02710.1016/j.endm.2013.05.027Search in Google Scholar

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

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

[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.11255710.1016/j.disc.2021.112557Search in Google Scholar

[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.Search in Google Scholar

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

[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.11252010.1016/j.disc.2021.112520Search in Google Scholar

• A Note About Monochromatic Components in Graphs of Large Minimum Degree

Recommended articles from Trend MD