In 2013, Goddard and Wash studied identifying codes in the Hamming graphs $K_q^n$. They stated, for instance, that $\gamma^{ID}(K_q^n)\leqslant q^{n-1}$ for any $q$ and $n\geqslant 3$. Moreover, they ...conjectured that $\gamma^{ID}(K_q^3)=q^2$. In this article, we show that $\gamma^{ID}(K_q^3)\leqslant q^2-q/4$ when $q$ is a power of four, which disproves the conjecture. Goddard and Wash also gave the lower bound $\gamma^{ID}(K_q^3)\geqslant q^2-q\sqrt{q}$. We improve this bound to $\gamma^{ID}(K_q^3)\geqslant q^2-\frac{3}{2} q$. Moreover, we improve the above mentioned bound $\gamma^{ID}(K_q^n)\leqslant q^{n-1}$ to $\gamma^{ID}(K_q^n)\leqslant q^{n-k}$ for $n=3\frac{q^k-1}{q-1}$ and to $\gamma^{ID}(K_q^n)\leqslant 3q^{n-k}$ for $n=\frac{q^k-1}{q-1}$, when $q$ is a prime power. For these bounds, we utilize two classes of closely related codes, namely, the self-identifying and the self-locating-dominating codes. In addition, we show that the self-locating-dominating codes satisfy the result $\gamma^{SLD}(K_q^3)=q^2$ related to the above conjecture.
The Jevons group
is an isometry group of the Hamming metric on the
-dimensional vector space
over
(2). It is generated by the group of all permutation (
×
)-matrices over
(2) and the translation ...group on
. Earlier the authors of the present paper classified the submetrics of the Hamming metric on
for
⩾ 4, and all overgroups of
which are isometry groups of these overmetrics. In turn, each overgroup of
is known to define orbital graphs whose “natural” metrics are submetrics of the Hamming metric. The authors also described all distance-transitive orbital graphs of overgroups of the Jevons group
. In the present paper we classify the distance-transitive orbital graphs of overgroups of the Jevons group. In particular, we show that some distance-transitive orbital graphs are isomorphic to the following classes: the complete graph
, the complete bipartite graph
, the halved (
+ 1)-cube, the folded (
+ 1)-cube, the graphs of alternating forms, the Taylor graph, the Hadamard graph, and incidence graphs of square designs.
The antibandwidth problem is to label vertices of graph
G
(
V
,
E
)
bijectively by integers
0
,
1
,
…
,
|
V
|
−
1
in such a way that the minimal difference of labels of adjacent vertices is ...maximised. In this paper we study the antibandwidth of Hamming graphs. We provide labeling algorithms and tight upper bounds for general Hamming graphs
∏
k
=
1
d
K
n
k
. We have exact values for special choices of
n
i
's and equality between antibandwidth and cyclic antibandwidth values.
For k ∈ ℤ
and G a simple, connected graph, a k-radio labeling f : V (G) → ℤ
of G requires all pairs of distinct vertices u and v to satisfy |f(u) − f(v)| ≥ k + 1 − d(u, v). We consider k-radio ...labelings of G when k = diam(G). In this setting, f is injective; if f is also surjective onto {1, 2, . . . , |V (G)|}, then f is a consecutive radio labeling. Graphs that can be labeled with such a labeling are called radio graceful. In this paper, we give two results on the existence of radio graceful Hamming graphs. The main result shows that the Cartesian product of t copies of a complete graph is radio graceful for certain t. Graphs of this form provide infinitely many examples of radio graceful graphs of arbitrary diameter. We also show that these graphs are not radio graceful for large t.
Hamming graph is known to be an important class of graphs, and it is a challenge to obtain algorithms that recognize whether a given graph
G
is a Hamming graph. Let
G
be a group and
S
⊆
G
be a ...nonempty subset of
G
. The Cayley graph with respect to
S
is a graph whose vertex set is
G
and arcset is the set of pairs (
u
,
v
) such that
v
=
s
u
for some element
s
∈
S
. This graph is denoted by
Cay
(
G
,
S
)
.Let
R
=
⊕
i
R
i
be a graded ring,
S
be the set of homogeneous elements of
R
,
S
′
a subset of
S
, and
S
′
′
=
⊕
i
≥
k
R
i
. In this paper, with a different view, we study
Cay
(
R
,
S
′
)
as a generalization of
Cay
(
R
,
S
)
to obtain a new point of view to study Cartesian products of complete graphs (Hamming graph). In particular, we show that any
Hamming graph
over sets of prime power sizes is isomorphic to
Cay
(
R
,
S
′
)
for some graded ring
R
and a subset
S
′
⊆
S
. Also we study
Cay
(
R
,
S
′
′
)
as another Cayley graph over graded rings and obtain relations between this graph and total, cototal and counit graphs.
We define the type of graph products, which enable us to treat many graph products in a unified manner. These unified graph products are shown to be compatible with Godsil–McKay switching. ...Furthermore, by this compatibility, we show that the Doob graphs can also be obtained from the Hamming graphs by switching.
Current High-Performance Computing (HPC) and data center networks rely on large-radix routers. Hamming graphs (Cartesian products of complete graphs) and dragonflies (two-level direct networks with ...nodes organized in groups) are some direct topologies proposed for such networks. The original definition of the dragonfly topology is very loose, with several degrees of freedom, such as the inter- and intragroup topology, the specific global connectivity, and the number of parallel links between groups (or trunking level). This work provides a comprehensive analysis of the topological properties of the dragonfly network, providing balancing conditions for network dimensioning, as well as introducing and classifying several alternatives for the global connectivity and trunking level. From a topological study of the network, it is noted that a Hamming graph can be seen as a canonical dragonfly topology with a high level of trunking. Based on this observation and by carefully selecting the global connectivity, the Dimension Order Routing (DOR) mechanism safely used in Hamming graphs is adapted to dragonfly networks with trunking. The resulting routing algorithms approximate the performance of minimal, nonminimal, and adaptive routings typically used in dragonflies but without requiring virtual channels to avoid packet deadlock, thus allowing for lower cost router implementations. This is obtained by properly selecting the link to route between groups based on a graph coloring of network routers. Evaluations show that the proposed mechanisms are competitive with traditional solutions when using the same number of virtual channels and enable for simpler implementations with lower cost. Finally, multilevel dragonflies are discussed, considering how the proposed mechanisms could be adapted to them.
Let
Γ
be a distance-semiregular graph on
Y
, and let
D
Y
be the diameter of
Γ
on
Y
. Let
Δ
be the halved graph of
Γ
on
Y
. Fix
x
∈
Y
. Let
T
and
T
′
be the Terwilliger algebras of
Γ
and
Δ
with ...respect to
x
, respectively. Assume, for an integer
i
with
1
≤
2
i
≤
D
Y
and for
y
,
z
∈
Γ
2
i
(
x
)
with
∂
Γ
(
y
,
z
)
=
2
, the numbers
|
Γ
2
i
-
1
(
x
)
∩
Γ
(
y
)
∩
Γ
(
z
)
|
and
|
Γ
2
i
+
1
(
x
)
∩
Γ
(
y
)
∩
Γ
(
z
)
|
depend only on
i
and do not depend on the choice of
y
,
z
. The first goal in this paper is to show the relations between
T
-modules of
Γ
and
T
′
-modules of
Δ
. Assume
Γ
is the incidence graph of the Hamming graph
H
(
D
,
n
) on the vertex set
Y
and the set
C
of all maximal cliques. Then,
Γ
satisfies above assumption and
Δ
is isomorphic to
H
(
D
,
n
). The second goal is to determine the irreducible
T
-modules of
Γ
. For each irreducible
T
-module
W
, we give a basis for
W
the action of the adjacency matrix on this basis and we calculate the multiplicity of
W
.
PDF
