The eigenvalues of the Hamming graph H(n,q) are known to be λi(n,q)=(q−1)n−qi, 0≤i≤n. The characterization of equitable 2-partitions of the Hamming graphs H(n,q) with eigenvalue λ1(n,q) was obtained ...by Meyerowitz (2003). We study the equitable 2-partitions of H(n,q) with eigenvalue λ2(n,q). We show that these partitions are reduced to equitable 2-partitions of H(3,q) with eigenvalue λ2(3,q) with the exception of two constructions.
On q-Ary Shortened-1-Perfect-Like Codes Shi, Minjia; Wu, Rongsheng; Krotov, Denis S.
IEEE transactions on information theory,
2022-Nov., 2022-11-00, Volume:
68, Issue:
11
Journal Article
Peer reviewed
Open access
We study codes with parameters of <inline-formula> <tex-math notation="LaTeX">q </tex-math></inline-formula>-ary shortened Hamming codes, i.e., <inline-formula> <tex-math ...notation="LaTeX">(n=(q^{m}-q)/(q-1), q^{n-m}, 3)_{q} </tex-math></inline-formula>. Firstly, we prove the fact mentioned in 1998 by Brouwer et al. that such codes are optimal, generalizing it to a bound for multifold packings of radius-1 balls, with a corollary for multiple coverings. In particular, we show that the punctured Hamming code is an optimal <inline-formula> <tex-math notation="LaTeX">q </tex-math></inline-formula>-fold packing with minimum distance 2. Secondly, for every admissible length starting from <inline-formula> <tex-math notation="LaTeX">n=20 </tex-math></inline-formula>, we show the existence of 4-ary codes with parameters of shortened 1-perfect codes that cannot be obtained by shortening a 1-perfect code.
Radio Number of Hamming Graphs of Diameter 3 DeVito, Jason; Niedzialomski, Amanda; Warren, Jennifer
Theory and applications of graphs (Statesboro, Ga.),
07/2022, Volume:
9, Issue:
2
Journal Article
Peer reviewed
Open access
For $G$ a simple, connected graph, a vertex labeling $f:V(G)\to \Z_+$ is called a \emph{radio labeling of $G$} if it satisfies $|f(u)-f(v)|\geq\diam(G)+1-d(u,v)$ for all distinct vertices $u,v\in ...V(G)$. The \emph{radio number of $G$} is the minimal span over all radio labelings of $G$. If a bijective radio labeling onto $\{1,2,\dots,|V(G)|\}$ exists, $G$ is called a \emph{radio graceful} graph. We determine the radio number of all diameter 3 Hamming graphs and show that an infinite subset of them is radio graceful.
The L-ary n-dimensional hamming graph KLn is one of the most attractive interconnection networks for parallel processing and computing systems. Analysis of the link fault tolerance of topology ...structure can provide the theoretical basis for the design and optimization of the interconnection networks. The k-component edge-connectivity cλk(G) of an interconnection network G, is the minimum number of set of faulty links, such that these malfunctions disconnect the network G with at least k connected subnetworks. It gives a more precise quantitative analysis of indicators of the robustness of a parallel distributed system in the event of faulty links. Let t=⌊n2⌋ if L is even, and t=⌈n2⌉ if L is odd. In this paper, we prove that the (k+1)-component edge-connectivity of L-ary n-dimensional hamming graphs is cλk+1(KLn)=(L−1)nk−exk(KLn)2 for k≤Lt, n≥7, where exk(KLn) represents the maximum degree sum of the subgraph induced by all k processors of KLn. As the exact values of (k+1)-component edge-connectivity of KLn oscillate greatly, an efficient O(logN) algorithm is designed to determine the exact values of cλk+1(KLn) for each k≤Lt and N=Ln. Our result improves those of Xu et al. 33 and Liu et al. 27.
•The (k+1)-component edge-connectivity of L-ary n-dimensional hamming graphs KLn is explored.•Determine the exact value of cλk+1(KLn) for each k≤Lt and n≥7, where t=⌊n2⌋ if L is even, and t=⌈n2⌉ if L is odd.•An efficient O(logN) algorithm is designed to determine the exact value of cλk+1(KLn) for each k≤Lt and N=Ln.
The geometry of diagonal groups Bailey, R. A.; Cameron, Peter J.; Praeger, Cheryl E. ...
Transactions of the American Mathematical Society,
08/2022, Volume:
375, Issue:
8
Journal Article
Peer reviewed
Open access
Diagonal groups are one of the classes of finite primitive permutation groups occurring in the conclusion of the O’Nan–Scott theorem. Several of the other classes have been described as the ...automorphism groups of geometric or combinatorial structures such as affine spaces or Cartesian decompositions, but such structures for diagonal groups have not been studied in general.
The main purpose of this paper is to describe and characterise such structures, which we call diagonal semilattices . Unlike the diagonal groups in the O’Nan–Scott theorem, which are defined over finite characteristically simple groups, our construction works over arbitrary groups, finite or infinite.
A diagonal semilattice depends on a dimension m and a group T. For m=2, it is a Latin square, the Cayley table of T, though in fact any Latin square satisfies our combinatorial axioms. However, for m \geqslant3, the group T emerges naturally and uniquely from the axioms. (The situation somewhat resembles projective geometry, where projective planes exist in great profusion but higher-dimensional structures are coordinatised by an algebraic object, a division ring.)
A diagonal semilattice is contained in the partition lattice on a set \Omega, and we provide an introduction to the calculus of partitions. Many of the concepts and constructions come from experimental design in statistics.
We also determine when a diagonal group can be primitive, or quasiprimitive (these conditions turn out to be equivalent for diagonal groups).
Associated with the diagonal semilattice is a graph, the diagonal graph, which has the same automorphism group as the diagonal semilattice except in four small cases with m\leqslant 3. The class of diagonal graphs includes some well-known families, Latin-square graphs and folded cubes, and is potentially of interest. We obtain partial results on the chromatic number of a diagonal graph, and mention an application to the synchronization property of permutation groups.
In this paper, we consider the minimal doubly resolving set problem in Hamming graphs, hypercubes and folded hypercubes. We prove that the minimal doubly resolving set problem in hypercubes is ...equivalent to the coin weighing problem. Then we answer an open question on the minimal doubly resolving set problem in hypercubes. We disprove a conjecture on the metric dimension problem in folded hypercubes and give some asymptotic results for the metric dimension and the minimal doubly resolving set problems in Hamming graphs and folded hypercubes by establishing connections between these problems. Using the Lindström’s method for the coin weighing problem, we give an efficient algorithm for the minimal doubly resolving set problem in hypercubes and report some new upper bounds. We also prove that the minimal doubly resolving set problem is NP-hard even restrict on split graphs, bipartite graphs and co-bipartite graphs.
The Hamming graph H(n,q) is the graph whose vertices are the words of length n over the alphabet {0,1,…,q−1}, where two vertices are adjacent if they differ in exactly one coordinate. The adjacency ...matrix of H(n,q) has n+1 distinct eigenvalues n(q−1)−q⋅i with corresponding eigenspaces Ui(n,q) for 0≤i≤n. In this work we study functions belonging to a direct sum Ui(n,q)⊕Ui+1(n,q)⊕⋯⊕Uj(n,q) for 0≤i≤j≤n. We find the minimum cardinality of the support of such functions for q=2 and for q=3, i+j>n. In particular, we find the minimum cardinality of the support of eigenfunctions from the eigenspace Ui(n,3) for i>n2. Using the correspondence between 1-perfect bitrades and eigenfunctions with eigenvalue −1, we find the minimum size of a 1-perfect bitrade in the Hamming graph H(n,3).
Perfect 2‐colorings of Hamming graphs Bespalov, Evgeny A.; Krotov, Denis S.; Matiushev, Aleksandr A. ...
Journal of combinatorial designs,
June 2021, 2021-06-00, 20210601, Volume:
29, Issue:
6
Journal Article
Peer reviewed
Open access
We consider the problem of existence of perfect 2‐colorings (equitable 2‐partitions) of Hamming graphs with given parameters. We start with conditions on parameters of graphs and colorings that are ...necessary for their existence. Next we observe known constructions of perfect colorings and propose some new ones giving new parameters. At last, we deduce which parameters of colorings are covered by these constructions and give tables of admissible parameters of 2‐colorings in Hamming graphs
H
(
n
,
q
) for small
n and
q. Using the connection with perfect colorings, we construct an orthogonal array OA(2048, 7, 4, 5).
In connection with his solution of the Sensitivity Conjecture, Hao Huang (arXiv: 1907.00847, 2019) asked the following question: Given a graph
G with high symmetry, what can we say about the smallest ...maximum degree of induced subgraphs of
G with
α
(
G
)
+
1 vertices, where
α
(
G
) denotes the size of the largest independent set in
G? We study this question for
H
(
n
,
k
), the
n‐dimensional Hamming graph over an alphabet of size
k. Generalizing a construction by Chung et al. (JCT‐A, 1988), we prove that
H
(
n
,
k
) has an induced subgraph with more than
α
(
H
(
n
,
k
)
) vertices and maximum degree at most
⌈
n
⌉. Chung et al. proved this statement for
k
=
2 (the
n‐dimensional cube).
PDF
