A note on the strength of a hypercube
Melissa A. Huggan, M.E. Messinger, Dylan Pearson · 2025
Read A note on the strength of a hypercube by Melissa A. Huggan, M.E. Messinger, Dylan Pearson (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-21908.txt.
Introduction
Melissa Huggan, Messinger, and Dylan Pearson tighten a bound on a labeling number for the hypercube, the graph formed by the corners of a many-dimensional cube. Their 2025 note treats the strength of a graph: label the vertices, add the labels of each joined pair, and take the largest such sum. The strength of the graph is the best score any labeling can force that maximum down to.
The hypercube's exact strength is unknown, with only bounds on record. The trio supply an improved upper bound, meaning a labeling scheme that keeps every edge sum at or below a lower ceiling than before. Notes of this kind chip away at extremal problems one bound at a time. The result adds to the theory of graph labelings begun as a generalization of super magic strength.
Catalog record
| CREATOR | Melissa A. Huggan, M.E. Messinger, Dylan Pearson |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-21908
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A note on the strength of a hypercube Melissa A. Huggan, M.E. Messinger, Dylan Pearson Abstract As a generalization of super magic strength, the strength of a graph was introduced in [ R. Ichishima, F.A. Muntaner-Batle, A. Oshima, Bounds for the strength of graphs, Austral. J. of Combin. 72(3) (2018) 492-508 ]. For a vertex ordering f f of graph G G , the strength of f f is the maximum sum of the labels on any pair of adjacent vertices. The strength of G G is defined as the minimum strength of f f , taken over all vertex orderings of G G . The strength of the hypercube is unknown, but bounded. In this note, we provide an improved upper bound for the strength of a hypercube. 1 Introduction Let G be a graph on n vertices and f be a bijective function f:V(G)\to\left\{1,2,\ldots,n\right\} . The strength of f , denoted \str_{f}(G) , is defined as \str_{f}(G)=\max\{f(u)+f(v):uv\in E(G)\}. The strength of G , denoted by \str(G) , is defined as \str(G)=\min\{\str_{f}(G):f\text{~is a vertex ordering of~}G\}. The strength of a graph was first defined in [ 4 ] and was motivated by super edge-magic labelings and the super magic strength of a graph. See the survey [ 6 ] for more on super edge-magic labelings and [ 1 , 4 ] for more on super magic strength. Ichishima et al. [ 4 ] determined the strength of a number of graph classes, including paths, cycles, complete graphs, and complete bipartite graphs. The strength of some trees, including caterpillars and complete n -ary trees was determined in [ 5 ] . The n -dimensional hypercube, denoted Q_{n} , is the graph whose vertices correspond to the (0,1) -binary strings of length n ; two vertices being adjacent if and only if the corresponding binary strings differ in exactly one digit. The n -dimensional hypercube, Q_{n} , was considered in [ 4 ] , where they proved the following. Theorem 1.1 ( [ 4 ] ) . For the n -dimensional hypercube Q_{n} , \str(Q_{1})=3 , \str(Q_{2})=6 , and for every integer n\geq 3 , 2^{n}+n\leq\str(Q_{n})\leq 2^{n}+2^{n-2}+1. For completeness, we note that the lower bound was improved in [ 2 , Theorems 16, 17, and Corollary 18] to the following. Theorem 1.2 ( [ 2 ] ) . For the n -dimensional hypercube Q_{n} , \str(Q_{3})=11 , \str(Q_{4})=21 , \str(Q_{5})=40 , \begin{array}[]{ll}\str(Q_{n})\geq 2^{n}+4n-12&\text{for $5\leq n\leq 9$, and}\\ \str(Q_{n})\geq 2^{n}+\lfloor\frac{n^{2}}{4}\rfloor+4&\text{for $n\geq 10$.}\end{array} In this note, we improve the upper bound for \str(Q_{n}) . We define a bijection f between the set of all n -bit strings and \{1,2,\dots,2^{n}\} . We first show the bijection gives the exact strength of Q_{3} , Q_{4} , and Q_{5} . We then determine the recurrence \str(Q_{n})\leq\str_{f}(Q_{n})\leq\str_{f}(Q_{n-2})+3\cdot 2^{n-2}+\binom{n-3}{\lceil\frac{n-3}{2}\rceil}+\binom{n-2}{\lceil\frac{n-2}{2}\rceil} in Corollary 2.9 . The recurrence provides an improvement over the upper bound of Theorem 1.1 of [ 4 ] for n\in\{5,6,\cdots,13\} . Ultimately, in Corollary 2.10 , we show that for all n\geq 14 , \str(Q_{n})\leq 2^{n}+2^{n-3}+28, which is an improvement of 2^{n-3}-27 over the upper bound of Theorem 1.1 of [ 4 ] . 2 An improved upper bound for \mathbf{str(Q_{n})} We state some important definitions before presenting the bijection between the n -bit strings and \left\{1,2,\ldots,2^{n}\right\} and proving some initial observations. Let x=x_{1}x_{2}\cdots x_{n} and y=y_{1}y_{2}\cdots y_{n} be distinct n -bit strings; that is, x_{i} , y_{i}\in\left\{0,1\right\} for every i\in\left\{1,2,\ldots,n\right\} . The Hamming weight , or simply weight of a bit string is the number of non-zero bits in the string. The Hamming distance between two n -bit strings x and y is the number of positions in which x and y differ. Consequently, two vertices of Q_{n} are adjacent if and only if the Hamming distance between the corresponding n -bit strings is one. We define x<y to be in lexicographic order if x_{i}=y_{i} for i<k and x_{k}<y_{k} for some k\leq n . We define reverse lexicographic order as the reverse ordering of the bit strings. That is, if x<y<z then the sequence (x,y,z) is in lexicographic order and the sequence (z,y,x) is in reverse lexicographic order. We will often refer to the lexicographic or reverse lexicographic ordering of the set of bit strings of a fixed length and weight, so we define S_{n}^{i} to be the sequence of n -bit strings of weight i , taken in lexicographic order; and R_{n}^{i} be the sequence of n -bit strings of weight i , taken in reverse lexicographic order. Finally, define S_{n} to be the sequence: S_{n}=\big(R_{n}^{1},R_{n}^{3},R_{n}^{5},\dots,R_{n}^{n-1},S_{n}^{n},S_{n}^{n-2},\dots,S_{n}^{4},S_{n}^{2},S_{n}^{0}\big)~~\text{for even $n$;} S_{n}=\big(R_{n}^{1},R_{n}^{3},R_{n}^{5},\dots,R_{n}^{n-2},R_{n}^{n},S_{n}^{n-1},\dots,S_{n}^{4},S_{n}^{2},S_{n}^{0}\big)~~\text{for odd $n$.} Observe that S_{n}^{n}=R_{n}^{n} since both contain only the string of weight n (i.e. the all 1 s string). Since every n -bit string appears exactly once in S_{n} we can define a bijection f between the sequence of all n -bit strings (in S_{n} ) and \{1,2,\dots,2^{n}\} . Note that the first 2^{n-1} strings in S_{n} each have odd weight and the second 2^{n-1} strings each have even weight. As an example, the sequences S_{n} for n=3,4,5,6 are given in Tables 1(a) , 1(b) , 1(c) , 1(d) , respectively. Although it is already known that \str(Q_{3})=11 , \str(Q_{4})=21 and \str(Q_{5})=40 , the reader can verify from Tables 1(a) , 1(b) , and 1(c) that these values are achieved using the bijection provided by S_{n} . The one’s complement of a binary string is the string obtained by flipping all the bits in the representation, for example, 1011 is the one’s complement of 0100 . We will represent the one’s complement of a string x as \overline{x} . For odd n , suppose x is an n -bit string with weight i for some odd positive integer i . Then x\in R_{n}^{i} and \overline{x}\in S_{n}^{n-i} and by construction of S_{n} , f(x)+2^{n-1}=f(\overline{x}). (1) bit string x f(x) bit string x f(x) 100 1 011 5 010 2 101 6 001 3 110 7 111 4 000 8 (a) Sequence S_{3} with R_{3}^{1} , R_{3}^{3} on the left, S_{3}^{2} , S_{3}^{0} on the right. bit string x f(x) 1000 1 0100 2 0010 3 0001 4 1110 5 1101 6 1011 7 0111 8 bit string x f(x) 1111 9 0011 10 0101 11 0110 12 1001 13 1010 14 1100 15 0000 16 (b) Sequence S_{4} with R_{4}^{1} , R_{4}^{3} on the left, S_{4}^{4} , S_{4}^{2} , S_{4}^{0} on the right. bit string x f(x) bit string x f(x) 10000 1 01111 17 01000 2 10111 18 00100 3 11011 19 00010 4 11101 20 00001 5 11110 21 11100 6 00011 22 11010 7 00101 23 11001 8 00110 24 10110 9 01001 25 10101 10 01010 26 10011 11 01100 27 01110 12 10001 28 01101 13 10010 29 01011 14 10100 30 00111 15 11000 31 11111 16 00000 32 (c) Sequence S_{5} with R_{5}^{1} , R_{5}^{3} , R_{5}^{5} on the left, S_{5}^{4} , S_{5}^{2} , S_{5}^{0} on the right. bit string x f(x) 100000 1 010000 2 001000 3 000100 4 000010 5 000001 6 111000 7 110100 8 110010 9 110001 10 101100 11 101010 12 101001 13 100110 14 100101 15 100011 16 011100 17 011010 18 011001 19 010110 20 010101 21 010011 22 001110 23 001101