Minimal binary 2-neighbour-transitive codes Hawtin, Daniel R.; Praeger, Cheryl E.
Journal of combinatorial theory. Series A,
April 2020, 2020-04-00, Volume:
171
Journal Article
Peer reviewed
Open access
The main result here is a characterisation of binary 2-neighbour-transitive codes with minimum distance at least 5 via their minimal subcodes, which are found to be generated by certain designs. The ...motivation for studying this class of codes comes primarily from their relationship to the class of completely regular codes. The results contained here yield many more examples of 2-neighbour-transitive codes than previous classification results of families of 2-neighbour-transitive codes. In the process, new lower bounds on the minimum distance of particular sub-families are produced. Several results on the structure of 2-neighbour-transitive codes with arbitrary alphabet size are also proved. The proofs of the main results apply the classification of minimal and pre-minimal submodules of the permutation modules over F2 for finite 2-transitive permutation groups.
Let $m>1$ be an integer and $\Omega$ be an $m$-set. The Hamming graph $H(n,m)$ has $\Omega ^{n}$ as its vertex-set, with two vertices are adjacent if and only if they differ in exactly one ...coordinate. In this paper, we provide a new proof on the automorphism group of the Hamming graph $H(n,m)$. Although our result is not new (CE Praeger, C Schneider, Permutation groups and Cartesian decompositions, Cambridge University Press, 2018), we believe that our proof is shorter and more elementary than the known proofs for determining the automorphism group of Hamming graph.
An L(h1,h2,…,hl)-labelling of a graph G is a mapping ϕ:V(G)→{0,1,2,…} such that for 1≤i≤l and each pair of vertices u,v of G at distance i, we have |ϕ(u)−ϕ(v)|≥hi. The span of ϕ is the difference ...between the largest and smallest labels assigned to the vertices of G by ϕ, and λh1,h2,…,hl(G) is defined as the minimum span over all L(h1,h2,…,hl)-labellings of G.
In this paper we study λh,1,…,1 for Cartesian products of graphs, where (h,1,…,1) is an l-tuple with l≥3. We prove that, under certain natural conditions, the value of this and three related invariants on a graph H which is the Cartesian product of l graphs attain a common lower bound. In particular, the chromatic number of the lth power of H equals this lower bound plus one. We further obtain a sandwich theorem which extends the result to a family of subgraphs of H which contain a certain subgraph of H. All these results apply in particular to the class of Hamming graphs: if q1≥⋯≥qd≥2 and 3≤l≤d then the Hamming graph H=Hq1,q2,…,qd satisfies λql,1,…,1(H)=q1q2…ql−1 whenever q1q2…ql−1>3(ql−1+1)ql…qd. In particular, this settles a case of the open problem on the chromatic number of powers of the hypercubes.
In this paper, we study the square of generalized Hamming graphs by the properties of abelian groups, and characterize some isomorphisms between the square of generalized Hamming graphs and the ...non-complete extended p-sum of complete graphs. As applications, we determine the eigenvalues of the square of some generalized Hamming graphs.
Weakly distance-regular digraphs are a natural directed version of distance-regular graphs. In Wang and Suzuki (Discrete Math 264:225–236, 2003), the third author and Suzuki proposed a question when ...an orientation of a distance-regular graph defines a weakly distance-regular digraph. In this paper, we initiate this project and classify all commutative weakly distance-regular digraphs whose underlying graphs are Hamming graphs, folded
n
-cubes and Doob graphs, respectively.
A
domatic
(
resp. total domatic
)
k
-
coloring
of a graph
G
is an assignment of
k
colors to the vertices of
G
such that each vertex contains vertices of all
k
colors in its closed neighborhood (resp. ...open neighborhood). The
domatic
(
resp. total domatic
)
number
of
G
, denoted
d
(
G
) (resp.
d
t
(
G
)
), is the maximum
k
for which
G
has a domatic (resp. total domatic)
k
-coloring. In this paper, we show that for two non-trivial graphs
G
and
H
, the domatic and total domatic numbers of their Cartesian product
G
□
H
is bounded above by
max
{
|
V
(
G
)
|
,
|
V
(
H
)
|
}
and below by
max
{
d
(
G
)
,
d
(
H
)
}
. Both these bounds are tight for an infinite family of graphs. Further, we show that if
H
is bipartite, then
d
t
(
G
□
H
)
is bounded below by
2
min
{
d
t
(
G
)
,
d
t
(
H
)
}
and
d
(
G
□
H
)
is bounded below by
2
min
{
d
(
G
)
,
d
t
(
H
)
}
. As a consequences, we get new bounds for the domatic and total domatic number of hypercubes and Hamming graphs of certain dimensions, and exact values for some
n
-dimensional tori which turns out to be a generalization of a result due to Gravier from 2002.
A generalization of a theorem of Hoffman Koolen, Jack H.; Yang, Qianqian; Yang, Jae Young
Journal of combinatorial theory. Series B,
March 2019, 2019-03-00, Volume:
135
Journal Article
Peer reviewed
Open access
In 1977, Hoffman gave a characterization of graphs with smallest eigenvalue at least −2. In this paper we generalize this result to graphs with smaller smallest eigenvalue. For the proof, we use a ...combinatorial object named Hoffman graph, introduced by Woo and Neumaier in 1995. Our result says that for every λ≤−2, if a graph with smallest eigenvalue at least λ satisfies some local conditions, then it is highly structured. We apply our result to graphs which are cospectral with the Hamming graph H(3,q), the Johnson graph J(v,3) and the 2-clique extension of grids, respectively.
A set X in the Euclidean space Rd is an m-distance set if the set of Euclidean distances between two distinct points in X has size m. An m-distance set X in Rd is maximal if there does not exist a ...vector x in Rd such that the union of X and {x} still has only m distances. Bannai et al. (2012) investigated maximal m-distance sets that contain the Euclidean representation of the Johnson graph J(n,m). In this paper, we consider the same problem for the Hamming graph H(n,m). The Euclidean representation of H(n,m) is an m-distance set in Rm(n−1). We prove that if the representation of H(n,m) is not maximal as an m-distance set for some m, then the maximum value of n is m2+m−1. Moreover we classify the largest m-distance sets that contain the representation of H(n,m) for n≥2 and m≤4. We also classify the maximal 2-distance sets that are in R2n−1 and contain the representation of H(n,2) for n≥2.
A
code
is a subset of the vertex set of a
Hamming graph
. The
set of
s
-neighbours
of a code is the set of all vertices at Hamming distance
s
from their nearest codeword. A code
C
is
s
-
elusive
if ...there exists a distinct code
C
′
that is equivalent to
C
under the full automorphism group of the Hamming graph such that
C
and
C
′
have the same set of
s
-neighbours. We show that the minimum distance of an
s
-elusive code is at most
2
s
+
2
, and that an
s
-elusive code with minimum distance at least
2
s
+
1
gives rise to a
q
-ary
t
-design with certain parameters. This leads to the construction of: an infinite family of 1-elusive and completely transitive codes, an infinite family of 2-elusive codes, and a single example of a 3-elusive code. Answers to several open questions on elusive codes are also provided.
PDF
