Nemanja Vučićević, Izudin Redžepović, Nenad Stojanović · match Communications in Mathematical and in Computer Chemistry · 2024
Hamming distance is a highly valuable quantity in computer science. In this work, we establish the Hamming matrix H of a graph G, H(G). This is a square matrix, where the elements of the H(G) are Hamming distances. Also, we define the Hamming energy of a graph, HE(G), which is a sum of the absolute eigenvalues of H(G). Finally, we present some bounds on the HE(G) and its predictive potential.
Cited by 1Open access
M. Saravanan, KM. Kathiresan · Iranian Journal of Mathematical Sciences and Informatics · 2025
The independence graph Ind(G) of a graph G is the graph with vertices as maximum independent sets of G and two vertices are adjacent, if and only if the corresponding maximum independent sets are disjoint.In this work, we find the independence graph of Cartesian product of d copies of complete graphs Kq, which is known as the Hamming graph H(d, q).Greenwell and Lovasz [7] found that the independence number of direct product of d copies of Kq as q d-1 .We prove that the independence number of Hamming graph H(d, q), which is cartesian product of d copies of Kq, is also q d-1 .As an application of our findings, we find answers for rook problem in higher dimensional square chess board.
Cited by 0Open access
Dominic van der Zypen · arXiv (Cornell University) · 2019
Graph embeddings deal with injective maps from a given simple, undirected graph $G=(V,E)$ into a metric space, such as $\mathbb{R}^n$ with the Euclidean metric. This concept is widely studied in computer science, see \cite{ge1}, but also offers attractive research in pure graph theory \cite{ge2}. In this note we show that any graph can be embedded into a particularly simple metric space: $\{0,1\}^n$ with the Hamming distance, for large enough $n$.
Cited by 0Open access
Harishchandra S. Ramane, Thippeswamy Shivaprasad, Sheena Y. Chowri · Creative Mathematics and Informatics · 2025
Let G be a graph with n vertices and m edges. Let V(G) = {v1,v2,...,vn} be the vertex set of G. Thestring s(vi) is the row in the incidence matrix of G corresponding to the vertex vi, which is an m-tuple in Zm 2 . The Hamming matrix H(G) = [hij] of a graph G is an n×nmatrix, whose (i,j)-th entry is the Hamming distance between the strings s(vi) and s(vj). The Hamming energy HE(G) of a graph G is the sum of the absolute values of the eigenvalues of H(G). Recently the Hamming energy is introduced and obtained bounds for it in terms of the Hammingindexandobservedits predictive potentiality by correlating the physicochemical properties of molecules. In this paper we give the better bound for Hamming energy in terms of number of vertices and edges. Also obtain the largest eigenvalue of the Hamming matrix of a regular graph. Further obtain explicitly the eigenvalues of the Hamming matrix and Hamming energy of a complete bipartite graph
Cited by 1Open access
Yichen Wang, Mengyu Cao, Zequn Lv et al. · The Electronic Journal of Combinatorics · 2026
Let $t,q$ and $n$ be positive integers. Write $[q] = \{1,2,\ldots,q\}$. The generalized Hamming graph $H(t,q,n)$ is the graph whose vertex set is the cartesian product of $n$ copies of $[q]$ $(q\ge 2)$, where two vertices are adjacent if their Hamming distance is at most $t$. In particular, $H(1,q,n)$ is the well-known Hamming graph and $H(1,2,n)$ is the hypercube. In 2006, Chandran and Kavitha described the asymptotic value of $tw(H(1,q,n))$, where $tw(G)$ denotes the treewidth of $G$. In this paper, we give the exact pathwidth of $H(t,2,n)$ and show that $tw(H(t,q,n)) = \Theta(tq^n/\sqrt{n})$ when $n$ goes to infinity. Based on those results, we show that the treewidth of bipartite Kneser graph $BK(n,k)$ is $\binom{n}{k} - 1$ when $n$ is sufficient large relative to $k$ and the bounds of $tw(BK(2k+1,k))$ are given. Moreover, we present the bounds of the treewidth of generalized Petersen graph.
Cited by 0Open access
Ju Zhang, Jin‐Xin Zhou, Jaeun Lee et al. · Discrete Mathematics · 2023
Cited by 3
Qiang Hua · 2001
In the expand-and-truncate learning algorithm (ETL), every true node set must be separated from the false node sets, and ETL is a learning algorithm of exhaustion. The Hamming-Graph Learning Algorithm (HGLA) is proposed in this paper. The n-dimension Hamming-Graph HG=V,E is an n-order regular graph to express n-dimension Hamming geometric space. The node-set V has 2 n nodes, and the Hamming distance between the two nodes connected by one side is equal to constant 1. If a core node V c in a HG is selected, and let its next adjacent nodes as its children, and so on, then, we get a directed HG. The sub-graph consisting of the core (and the root) node V c, and all of its true children is called the first level Sub-Hamming-Graph of HG, the SHG1. The vertices inside a SHG1 of the n-dimension HG can surely be separated from the vertices outside SHG1 by a hyperplane. Thus, it can be expressed using one hidden neuron. And if it can be expanded as large as possible, then, the structure of binary neural network can be best optimized. But, whether one SHGL can be separated from the vertices outside by a hyperplane when L1 is not sure. Without some conditions to select the core node and to expand the SHG1, the learning algorithm of BNN will still be exhaustive. Therefore, a true node that has the most true-nodes adjacent should be selected as the core node V c. And if there are more than one such node, the one within them that has the most adjacent nodes each other should be selected. Only the true nodes all of whose parents have been within the SHGL could be expanded, and every step of the expansion should be tested using the criterion min{H y|V y∈SHGL}max{H z|V z∈～SHGL} (formula 5). If SHGL is formed and mostly expanded according to these conditions, and if it is linear separable, it must be the biggest true nodes set in the SHGL that can be linear separated from the others. Being not exhaustive, HGLA is a fast learning algorithm. Two examples in the references are tested and compared using HGLA and ETL. For example A(A 7-Bit Binary Function), HGLA requires only 3 hidden neurons but ETL requires 7; For example B(Approximation of a Circular Region), HGLA demands only 4 hidden neurons, but ETL requires 5; and the output neuron of HGLA needs not be trained, so it is optimized.
Cited by 0
Masato Tomiyama · Journal of Algebraic Combinatorics · 2017
Cited by 5
Mihyun Kang, Michael Missethan, Dominik Schmid · SIAM Journal on Discrete Mathematics · 2025
Cited by 0Open access
Panfeng Chen, Yisong Wang, Quan Yu et al. · IEEE Access · 2020
Knowledge graphs (KGs) play an important role in many real-world applications like information retrieval, question answering, relation extraction, etc. To reveal implicit knowledge from a knowledge graph (KG), viz. knowledge graph completion (KGC), is a crucial task for the downstream applications based on KG. For this purpose various embedding-based approaches have been proposed recently. This paper proposes a new approach named HRESCAL to KGC. It extends the well-known embedding-based approach RESCAL by introducing Hamming distance-based encoder to capture implicit multihop and partial inverse relation features in a KG. Experimental results on widely used KGC benchmarks show that the new approach achieves state-of-the-art or is competitive AUC performance.
Cited by 9Open access
Fernando Levstein, Javier Hérnan Lezama, Ana Carolina Maldonado et al. · CONICET Digital (CONICET) · 2015
In this paper a lossy image compression methodusing the adjacency matrix of a graph is proposed.We instantiate the method using the Hamming graph,which gives rise to an image compression algorithmthat uses a Hadamard Matrix together with a thresholdapproach. In threshold methods, selection of thecorrect (static) threshold value is difficult. In our approachwe use a new threshold determination thatchanges from block to block obtaining an algorithmthat uses only integer and modular operations andobtains good results in some standard images. Thenew method has better stability under recompressioniteration than jpg.
Cited by 3Open access
Artur Schaefer · arXiv (Cornell University) · 2016
In this paper we determine all singular endomorphisms of the Hamming graph and other related graphs. The Hamming graph has vertices $\mathbb{Z}^{m}_n$ where two vertices are adjacent, if their Hamming distance is $1$. We show that its singular endomorphisms are uniform (each kernel has the same size) and that they are induced by Latin hypercubes (which essentially determines the number of singular endomorphisms). However, we do the same for its complement and some related graphs where the Hamming distance is allowed to be one of $1,...,k$, for some $1\leq k\leq m-1$. Ultimately, we consider the same situation where the vertices are tuples in $\mathbb{Z}_{n_1}\times\mathbb{Z}_{n_2}\times\cdots \times\mathbb{Z}_{n_m}$ (not all $n_i$ are equal).
Cited by 1Open access
Izudin Redžepović, Nemanja Vučićević, Nenad Stojanović · Scientific Publications of the State University of Novi Pazar Series A Applied Mathematics Informatics and mechanics · 2024
A novel graph quantity, named Hamming energy of a graph HE(G), has been proposed. It is defined as a sum of the absolute values of the eigenvalues of the Hamming matrix. To be used in chemistry, graph quantity should be able to discriminate between different isomers, i.e., it should be sensitive. Therefore, in this paper, we investigate the sensitivity of HE(G), using different sets of isomers. It was found that HE(G) shows exceptional sensitivity compared to graph energy and other eigenvalue-based graph quantities.
Cited by 0Open access
Shahram Mehry, Saadoun Mahmoudi · Bulletin of the Malaysian Mathematical Sciences Society · 2021
Cited by 1
Lorenzo Federico, Remco van der Hofstad, Tim Hulshof · Electronic Communications in Probability · 2016
We study the connectivity of random subgraphs of the $d$-dimensional Hamming graph $H(d, n)$, which is the Cartesian product of $d$ complete graphs on $n$ vertices. We sample the random subgraph with an i.i.d. Bernoulli bond percolation on $H(d,n)$ with parameter $p$. We identify the window of the transition: when $ np- \log n \to - \infty $ the probability that the graph is connected tends to $0$, while when $ np- \log n \to + \infty $ it converges to $1$. We also investigate the connectivity probability inside the critical window, namely when $ np- \log n \to t \in \mathbb{R} $. We find that the threshold does not depend on $d$, unlike the phase transition of the giant connected component of the Hamming graph (see [1]). Within the critical window, the connectivity probability does depend on $d$. We determine how.
Cited by 4Open access
N. Jacobsen · 2021
Probabilistic graphical models are used extensively across the information theory, artificial intelligence and machine learning disciplines. In this paper, we work towards realizing a generalized graph-based framework for automated learning in intelligent systems. The proposed automatic graph learning framework employs factor graphs, i.e. Tanner graphs from coding theory, to represent an arbitrary stochastic system of variables and factorized realizations of their joint probability density function. We develop algorithms that are capable of learning statistical relationships between system variables, which involves constructing an appropriate factor graph representation and generating estimates of its component probability density functions, from training data. In this paper, automatic graph learning is used to reverse engineer the Hamming code, based on training data comprised of input-output codeword pairs. We show that automatic graph learning is capable of replicating known decoder performance with an order of magnitude less training data than a multi-layer dense neural network.
Cited by 0
Jun Hu, Gengsheng Zhang, Bo Hou · Discrete Mathematics · 2026
Cited by 0
Lorenzo Federico, Remco van der Hofstad, Tim Hulshof · arXiv (Cornell University) · 2015
We study the connectivity of random subgraphs of the $d$-dimensional Hamming graph $H(d, n)$, which is the Cartesian product of $d$ complete graphs on $n$ vertices. We sample the random subgraph with an i.i.d.\ Bernoulli bond percolation on $H(d,n)$ with parameter $p$. We identify the window of the transition: when $ np- \log n \to - \infty$ the probability that the graph is connected goes to $0$, while when $ np- \log n \to + \infty$ it converges to $1$. We also investigate the connectivity probability inside the critical window, namely when $ np- \log n \to t \in \mathbb{R}$. We find that the threshold does not depend on $d$, unlike the phase transition of the giant connected component the Hamming graph (see [Bor et al, 2005]). Within the critical window, the connectivity probability does depend on d. We determine how.
Cited by 0Open access
Patrick Iff, Maciej Besta, Matheus Cavalcante et al. · arXiv (Cornell University) · 2022
Chips with hundreds to thousands of cores require scalable networks-on-chip (NoCs). Customization of the NoC topology is necessary to reach the diverse design goals of different chips. We introduce sparse Hamming graph, a novel NoC topology with an adjustable costperformance trade-off that is based on four NoC topology design principles we identified. To efficiently customize this topology, we develop a toolchain that leverages approximate floorplanning and link routing to deliver fast and accurate cost and performance predictions. We demonstrate how to use our methodology to achieve desired cost-performance trade-offs while outperforming established topologies in cost, performance, or both.
Cited by 0Open access
Konstantin Vorob’ev · Journal of Applied and Industrial Mathematics · 2014
Under study is the relationship between the eigenfunctions of the Johnson and Hamming graphs. An eigenfunction of a graph is an eigenvector of its adjacency matrix with some eigenvalue; moreover, an eigenfunction can be identically zero. We find a criterion for the embeddability of an eigenfunction of the Johnson graph J(n, w) with a given eigenvalue into a certain eigenfunction of the Hamming graph with a given eigenvalue.
Cited by 1