We study functions defined on the vertices of the Hamming graphs H(n,q). 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 consider the problem of finding the minimum possible support (the number of nonzeros) of functions belonging to a direct sum Ui(n,q)⊕Ui+1(n,q)⊕⋯⊕Uj(n,q) for 0≤i≤j≤n. For the case i+j≤n and q≥3 we find the minimum cardinality of the support of such functions and obtain a characterization of functions with the minimum cardinality of the support. In the case i+j>n and q≥4 we also find the minimum cardinality of the support of functions, and obtain a characterization of functions with the minimum cardinality of the support for i=j, i>n2 and q≥5. In particular, we characterize eigenfunctions from the eigenspace Ui(n,q) with the minimum cardinality of the support for cases i≤n2, q≥3 and i>n2, q≥5.
Let G be a graph. The 2-token graphF2(G) of G is with vertex set all the 2-subsets of V(G) such that two 2-subsets are adjacent if their symmetric difference is exactly an edge of G. In this paper, ...the full automorphism group of the 2-token graph of the Hamming graph is determined.
We introduce the notion of Levenshtein graphs, an analog to Hamming graphs but using the edit distance instead of the Hamming distance; in particular, vertices in Levenshtein graphs may be strings ...(i.e., words or sequences of characters in a reference alphabet) of possibly different lengths. We study various properties of these graphs, including a necessary and sufficient condition for their shortest path distance to be identical to the edit distance, and characterize their automorphism group and determining number. We also bound the metric dimension (i.e. minimum resolving set size) of Levenshtein graphs. Regarding the latter, recall that a run is a string composed of identical characters. We construct a resolving set of two-run strings and an algorithm that computes the edit distance between a string of length k and any single-run or two-run string in O(k) operations.
A k-independent set in a connected graph is a set of vertices such that any two vertices in the set are at distance greater than k in the graph. The k-independence number of a graph, denoted αk, is ...the size of a largest k-independent set in the graph. Recent results have made use of polynomials that depend on the spectrum of the graph to bound the k-independence number. They are optimized for the cases k=1,2. There are polynomials that give good (and sometimes) optimal results for general k, including case k=3. In this paper, we provide the best possible bound that can be obtained by choosing a polynomial for case k=3 and apply this bound to well-known families of graphs including the Hamming graph.
•In this paper, we characterize Hamming and Johnson graphs by their spectral gap.•We confirm Babai's conjecture on the motion of distance-regular graphs of bounded diameter.•Our characterization of ...Hamming graphs involves only inequality constraints.
One of the central results in the representation theory of distance-regular graphs classifies distance-regular graphs with μ≥2 and second largest eigenvalue θ1=b1−1. In this paper we give a classification under the (weaker) approximate eigenvalue constraint θ1≥(1−ε)b1 for the class of geometric distance-regular graphs. As an application, we confirm Babai's conjecture on the minimal degree of the automorphism group of distance-regular graphs of bounded diameter. This conjecture asserts that if X is a primitive distance-regular graph with n vertices, and X is not a Hamming graph or a Johnson graph, then the automorphism group Aut(X) has minimal degree ≥cn for some constant c>0. It follows that Aut(X) satisfies strong structural constraints.
We prove a conjecture by Van Dam & Sotirov on the smallest eigenvalue of (distance-j) Hamming graphs and a conjecture by Karloff on the smallest eigenvalue of (distance-j) Johnson graphs. More ...generally, we study the smallest eigenvalue and the second largest eigenvalue in absolute value of the graphs of the relations of classical P- and Q-polynomial association schemes.
For every graph
G $G$, let
α
(
G
) $\alpha (G)$ denote its independence number. What is the minimum of the maximum degree of an induced subgraph of
G $G$ with
α
(
G
)
+
1 $\alpha (G)+1$ vertices? We ...study this question for the
n $n$‐dimensional Hamming graph over an alphabet of size
k $k$. In this paper, we give a construction to prove that the answer is 1 for all
n $n$ and
k $k$ with
k
≥
3 $k\ge 3$. This is an improvement over an earlier work showing that the answer is at most
⌈
n
⌉ $\lceil \sqrt{n}\rceil $.
We study Cayley graphs of abelian groups from the perspective of quantum symmetries. We develop a general strategy for determining the quantum automorphism groups of such graphs. Applying this ...procedure, we find the quantum symmetries of the halved cube graph, the folded cube graph, and the Hamming graphs.
Models of sequence evolution typically assume that all sequences are possible. However, restriction enzymes that cut DNA at specific recognition sites provide an example where carrying a recognition ...site can be lethal. Motivated by this observation, we studied the set of strings over a finite alphabet with
taboos
, that is, with prohibited substrings. The taboo-set is referred to as
T
and any allowed string as a taboo-free string. We consider the so-called Hamming graph
Γ
n
(
T
)
, whose vertices are taboo-free strings of length
n
and whose edges connect two taboo-free strings if their Hamming distance equals one. Any (random) walk on this graph describes the evolution of a DNA sequence that avoids taboos. We describe the construction of the vertex set of
Γ
n
(
T
)
. Then we state conditions under which
Γ
n
(
T
)
and its suffix subgraphs are connected. Moreover, we provide an algorithm that determines if all these graphs are connected for an arbitrary
T
. As an application of the algorithm, we show that about
87
%
of bacteria listed in REBASE have a taboo-set that induces connected taboo-free Hamming graphs, because they have less than four type II restriction enzymes. On the other hand, four properly chosen taboos are enough to disconnect one suffix subgraph, and consequently connectivity of taboo-free Hamming graphs could change depending on the composition of restriction sites.
PDF
