Search

How to efficiently represent a graph in computer memory is a fundamental data structuring question. In the present paper, we address this question from a combinatorial point of view. A representation of an n -vertex graph G is called implicit if it assigns to each vertex of G a binary code of length O (log ⁡ n) so that the adjacency of two vertices is a function of their codes. A necessary condition for a hereditary class X of graphs to admit an implicit representation is that X has at most factorial speed of growth. This condition, however, is not sufficient, as was recently shown in [19]. Several sufficient conditions for the existence of implicit representations deal with boundedness of some parameters, such as degeneracy or clique-width. In the present paper, we analyze more graph parameters and prove a number of new results related to implicit representation and factorial properties. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a simple graph with vertex set as V and edge set as E. Within the framework of graph-based binary coding, a graph G is a threshold graph if and only if it can be generated by a binary code of the type 0 s 1 1 t 1 ... 0 s k 1 t k , where s i and t i are positive integers with 1 ≤ i ≤ k. This type of binary code is called a binary generating code of G. In this paper, we address a problem originally posed by Harary and Schwenk in [10] titled "Which graphs have integral spectra?" in which the main focus of our investigations lies in the Seidel Laplacian spectrum of G generated by 0 s 1 1 t 1 ... 0 s k 1 t k . We establish that all eigenvalues of G are integers and multiplicities of eigenvalues are equal to powers of bits 0 and 1 (sizes of strings of 0's and 1's) involved in a binary generating code of G. We exhibit a necessary and sufficient condition in terms of eigenvalues of the matrix associated with a graph-based G binary code to be Seidel Laplacian integral. Furthermore, for any prime p , we explore the Seidel Laplacian spectrum of zero-divisor graphs associated with the ring Z p m (where m is a positive integer) and the polynomial ring Z p [ x ] / (x p). [ABSTRACT FROM AUTHOR]

This paper constructs a class of lattices whose discrete analogues are variable-length non-linear codes. The well-known discrete analogue of lattices and linear codes inspires our approach. We next design a variable length binary non-linear code called automorphism orbit code from a finite abelian p -group of rank greater than 1, where p is a prime. For each finite abelian p -group, codewords of the automorphism orbit code are variable-length codewords called automorphism orbit codewords. The homomorphisms between groups determine homomorphism codes , whereas automorphism orbit codes are specified by partitions of a number, orbits of group action, homomorphisms and automorphisms of groups. For some groups G and H , we shall use elements of H o m (G , H) to create a cover relation for bit strings of codewords of an automorphism orbit code and formulate a lattice of variable length non-linear codes. [ABSTRACT FROM AUTHOR]

In two previous papers we constructed new families of completely regular codes by concatenation methods. Here we determine cases in which the new codes are completely transitive. For these cases we also find the automorphism groups of such codes. For the remaining cases, we show that the codes are not completely transitive assuming an upper bound on the order of the monomial automorphism groups, according to computational results. [ABSTRACT FROM AUTHOR]

Based on good algebraic structures and practicabilities, generalized quasi-cyclic (GQC) codes play important roles in coding theory. In this paper, we study some results on GQC codes over Z 4 including normalized generating sets, minimal generating sets and normalized generating sets of their dual codes. As an application, new Z 4 -linear codes and good binary nonlinear codes are constructed from GQC codes over Z 4. [ABSTRACT FROM AUTHOR]

In this paper, we always assume that p and n > 3 are two distinct odd primes, m ≥ 2 is a positive integer, and gcd ⁡ (p m , 2 n (2 2 n − 1)) ≠ 1. Set r = p 2 or r = p 3 , we determine upper bounds on the number of inequivalent extended binary irreducible Goppa codes Γ (L , g) of degree r and length 2 n + 1 , where L = F 2 n ∪ { ∞ } is the support set and each g (x) is an irreducible polynomial of degree r over F 2 n . [ABSTRACT FROM AUTHOR]

In this paper, we consider q -ary codes of length n and minimum Hamming distance d , which have two weights w 1 and w 2. These codes are denoted by (n , d , { w 1 , w 2 }) q codes. Let A q (n , d , { w 1 , w 2 }) denote the largest possible number of codewords in an (n , d , { w 1 , w 2 }) q code and we simply write A (n , d , { w 1 , w 2 }) for A 2 (n , d , { w 1 , w 2 }). Some upper bounds on A q (n , d , { w 1 , w 2 }) are given. The equivalences between binarytwo-weight codes and special combinatorial configurations with certain properties are established and then new upper bounds on A (n , d , { w 1 , w 2 }) are derived. For w 1 , w 2 ∈ { 2 , 3 , 4 } , optimal constructions of (n , d , { w 1 , w 2 }) 2 codes are presented. The exact value of A (n , d , { 2 , 3 }) is completely determined for all n and d. We determine the exact value of A (n , d , { 2 , 4 }) for any positive integer n ≡ 2 , 4 (mod 6) and d ∈ { 3 , 4 }. The exact value of A (n , d , { 3 , 4 }) is determined for any integer n and d ∈ { 6 , 7 } , or d = 5 and n ≡ 0 , 2 , 3 , 11 (mod 12). [ABSTRACT FROM AUTHOR]

Bose-Chaudhuri-Hocquenghem (BCH) codes have been intensively investigated. Even so, there is only a little known about primitive BCH codes, let alone non-primitive ones. In this paper, let q > 2 be a prime power, the dimension of a family of non-primitive BCH codes of length n = q m + 1 (also called antiprimitive) is studied. These codes are also linear codes with complementary duals (called LCD codes). Through some approaches such as iterative algorithm, partition and scaling, all coset leaders of C x modulo n with q ⌈ m 2 ⌉ < x ≤ 2 q ⌈ m 2 ⌉ + 2 are given for m ≥ 4. And for odd m the first several largest coset leaders modulo n are determined. Furthermore, a new kind of sequences is introduced to determine the second largest coset leader modulo n with m even and q odd. Also, for even m some conjectures about the first several coset leaders modulo n are proposed, whose complete verification would wipe out the difficult problem to determine the first several coset leaders of antiprimitive BCH codes. After deriving the cardinalities of the coset leaders, we shall calculate exact dimensions of many antiprimitive LCD BCH codes. [ABSTRACT FROM AUTHOR]

In this paper, we introduce Toeplitz codes of index t , which are a generalization of quasi-cyclic codes of index t. We show that such codes meet the asymptotic Gilbert-Varshamov bound on the relative distance with asymptotic rate 1 t over F q , so they are asymptotically good for any t. We characterize some special classes of Toeplitz codes as LCD codes (resp. linear codes with one-dimensional hull or self-orthogonal codes). It is worth mentioning that we determine the hull dimension of the isometric image of a linear code. Some optimal or almost optimal binary linear codes are obtained as a result. Most importantly, we obtain some optimal or almost optimal LCD codes (resp. linear codes with one-dimensional hull) from quasi-cyclic codes. In particular, we construct binary LCD [ 32 , 16 , 8 ] , [ 33 , 11 , 11 ] and [ 34 , 17 , 8 ] codes with improved parameters directly. [ABSTRACT FROM AUTHOR]

Abstract Let p be an odd prime, s , m be positive integers, γ , λ be nonzero elements of the finite field F p m such that γ p s = λ. In this paper, we show that, for any positive integer η , the Hamming distances of all repeated-root λ -constacyclic codes of length η p s can be determined by those of certain simple-root γ -constacyclic codes of length η. Using this result, Hamming distances of all constacyclic codes of length 4 p s are obtained. As an application, we identify all MDS λ -constacyclic codes of length 4 p s. [ABSTRACT FROM AUTHOR]

In this paper, we present a new bordered construction for self-dual codes which employs λ -circulant matrices. We give the necessary conditions for our construction to produce self-dual codes over a finite commutative Frobenius ring of characteristic 2. Moreover, using our bordered construction together with the well-known building-up and neighbour methods, we construct many binary self-dual codes of lengths 56, 62, 78, 92 and 94 with parameters in their weight enumerators that were not known in the literature before. [ABSTRACT FROM AUTHOR]

Linear complementary pair (LCP) of codes and rank metric codes over finite fields have been intensively investigated recently due to their applications in cryptography. In this paper, we first give the definition of LCP of rank-metric codes combined by the LCP of codes and rank-metric codes, and we establish the relationship between LCP of Delsarte codes and LCP of Gabidulin codes. We then present a criterion for Gabidulin codes (C , D) to be LCP. Using this criterion, we obtain two classes of LCP MRD of Gabidulin codes. Finally, we exhibit an interesting application of LCP MRD of Gabidulin codes in coding for the two-user binary adder channel. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of determining the exact value of A 2 (n , { d 1 , d 2 }) defined as the maximal cardinality of a binary code of length n with two possible distances d 1 and d 2. We prove that if d 2 > 2 d 1 , one has A 2 (n , { d 1 , d 2 }) ≤ n + 1. A similar bound holds for codes with d 1 ≢ d 2 (mod 2) : A 2 (n , { d 1 , d 2 }) ≤ { n + 1 for d 1 even, n + 2 for d 1 odd. Furthermore, we settle two conjectures left open by earlier authors that imply the following exact values: A 2 (n , { 2 , d }) = { ( n 2 ) + 1 for d = 4 and n ≥ 6 , n for 4 < d < n − 1 , n + 1 for d = n − 1 , and provide combinatorial constructions that improve on the lower bounds on A 2 (n , { d 1 , d 2 }) known so far. Finally, we prove the general upper bound A 2 (n , { d 1 , d 2 }) ≤ (n + 1) (n + 2) 2. [ABSTRACT FROM AUTHOR]

In the past few years, linear codes with few weights constructed from defining-sets have been extensively studied. In this paper, we further investigate a class of two-weight or three-weight linear codes from defining sets and determine their weight and complete weight enumerators by application of the theory of quadratic forms and some special Weil sums over finite fields. This paper generalizes some results in Jian et al. (2019), Yang (2020) and Zhu and Xu (2017). The parameters and weight distributions of the punctured codes of the discussed linear codes are also determined, and some optimal codes with respect to the Griesmer bound and some strongly regular graphs from two-weight projective codes are obtained. [ABSTRACT FROM AUTHOR]

Switching is a local transformation of a combinatorial structure that does not alter the main parameters. Switching of binary covering codes is studied here. In particular, the well-known transformation of error-correcting codes by adding a parity-check bit and deleting one coordinate is applied to covering codes. Such a transformation is termed a semiflip, and finite products of semiflips are semiautomorphisms. It is shown that for each code length n ≥ 3 , the semiautomorphisms are exactly the bijections that preserve the set of r -balls for each radius r . Switching of optimal codes of size at most 7 and of codes attaining K ( 8 , 1 ) = 32 is further investigated, and semiautomorphism classes of these codes are found. The paper ends with an application of semiautomorphisms to the theory of normality of covering codes. [ABSTRACT FROM AUTHOR]

This paper completes the enumeration of quasi-symmetric 2- ( 64 , 24 , 46 ) designs supported by the dual code C ⊥ of the binary linear code C spanned by the lines of A G ( 3 , 4 ) , initiated in Rodrigues and Tonchev (2015). It is shown that C ⊥ supports exactly 30,264 nonisomorphic quasi-symmetric 2- ( 64 , 24 , 46 ) designs. The automorphism groups of the related strongly regular graphs are computed. [ABSTRACT FROM AUTHOR]

Boolean functions have important applications in cryptography and coding theory. Two famous classes of binary codes derived from Boolean functions are the Reed–Muller codes and Kerdock codes. In the past two decades, a lot of progress on the study of applications of Boolean functions in coding theory has been made. Two generic constructions of binary linear codes with Boolean functions have been well investigated in the literature. The objective of this paper is twofold. The first is to provide a survey on recent results, and the other is to propose open problems on one of the two generic constructions of binary linear codes with Boolean functions. These open problems are expected to stimulate further research on binary linear codes from Boolean functions. [ABSTRACT FROM AUTHOR]

The idea of implicit representation of graphs was introduced in Kannan et al. (1992) and can be defined as follows. A representation of an n -vertex graph G is said to be implicit if it assigns to each vertex of G a binary code of length O ( log n ) so that the adjacency of two vertices is a function of their codes. Since an implicit representation of an n -vertex graph uses O ( n log n ) bits, any class of graphs admitting such a representation contains 2 O ( n log n ) labelled graphs with n vertices. In the terminology of Balogh et al. (2000) such classes have at most factorial speed of growth. In this terminology, the implicit graph conjecture can be stated as follows: every class with at most factorial speed of growth which is hereditary admits an implicit representation. The question of deciding whether a given hereditary class has at most factorial speed of growth is far from being trivial. In the present paper, we introduce a number of tools simplifying this question. Some of them can be used to obtain a stronger conclusion on the existence of an implicit representation. We apply our tools to reveal new hereditary classes with the factorial speed of growth. For many of them we show the existence of an implicit representation. [ABSTRACT FROM AUTHOR]

In this paper, we construct two new symmetric designs with parameters 2- (176 , 50 , 14) as designs invariant under certain subgroups of the full automorphism group of the Higman design. One is self-dual and has the full automorphism group of order 11520 and the other one is not self-dual and has the full automorphism group of order 2520. [ABSTRACT FROM AUTHOR]

In this paper, we construct self-dual codes from a construction that involves both block circulant matrices and block quadratic residue circulant matrices. We provide conditions when this construction can yield self-dual codes. We construct self-dual codes of various lengths over F 2 and F 2 + u F 2. Using extensions, neighbours and sequences of neighbours, we construct many new self-dual codes. In particular, we construct one new self-dual code of length 66 and 51 new self-dual codes of length 68. [ABSTRACT FROM AUTHOR]

As a further development and deepening of two examples in the paper (Fan and Zhang, 2017), we construct MDS Galois self-dual constacyclic codes over finite fields. First, we give the definition of normal MDS constacyclic codes and explore their existence conditions. Further, we give existence conditions for normal MDS Galois self-dual constacyclic codes. Based on the latter conditions, we classify and construct all normal MDS Galois self-dual λ -constacyclic codes over F q of length n , where q = p e is an odd prime power, gcd (q , n) = 1 and λ ∈ F q ∗ . [ABSTRACT FROM AUTHOR]

Let R = F 2 + u F 2 (u 2 = 0) and S = F 2 + u F 2 + u 2 F 2 (u 3 = 0) be two finite commutative chain rings. This paper studies F 2 R S -cyclic codes, which are described as S [ x ] -submodules of the S [ x ] -module F 2 [ x ] ∕ 〈 x r − 1 〉 × R [ x ] ∕ 〈 x s − 1 〉 × S [ x ] ∕ 〈 x t − 1 〉. We study their generator polynomials and the minimal generating sets. We classify each case of the generating sets separately and determine the size of each such case. Free F 2 R S -cyclic codes and separable codes are discussed, and the structural properties of dual codes of free F 2 R S -cyclic codes are investigated. Moreover, we determine the relationship between the generator polynomials of free F 2 R S -cyclic codes and their duals. As applications, we provide several examples of optimal and near-optimal binary codes which are obtained from the Gray images of F 2 R S -cyclic codes. [ABSTRACT FROM AUTHOR]

In this paper, we obtain explicit mass formulae for all Euclidean self-orthogonal and self-dual codes of an arbitrary length over finite commutative chain rings of odd characteristic. With the help of these mass formulae, we classify all Euclidean self-orthogonal and self-dual codes of lengths 2 , 3 , 4 , 5 over the chain ring F 5 [ u ] ∕ < u 2 > and of lengths 2 , 3 , 4 over the chain ring F 7 [ u ] ∕ < u 2 >. [ABSTRACT FROM AUTHOR]

Let p be a prime number, in this paper, we investigate the structures of all constacyclic codes of length p s over the ring R u 2 , v 2 , p m = F p m u , v ∕ 〈 u 2 , v 2 , u v − v u 〉. The units of the ring R u 2 , v 2 , p m can be divided into following five forms: α , λ 1 = α + δ 1 u v , λ 2 = α + γ v + δ u v , λ 3 = α + β u + δ u v , λ 4 = α + β u + γ v + δ u v , where α , β , γ , δ 1 ∈ F p m ∗ and δ ∈ F p m . We obtain the algebraic structures of all constacyclic codes of length p s over R u 2 , v 2 , p m , except (α + δ 1 u v) -constacyclic codes, in terms of their polynomial generators and also find the number of codewords in each of these constacyclic codes. The number of constacyclic codes and duals of constacyclic codes corresponding to the units λ 2 , λ 3 and λ 4 are determined. We also provide examples to illustrate our results, which include several optimal codes. [ABSTRACT FROM AUTHOR]

Let p be a prime, s , m be positive integers, λ be a nonzero element of the finite field F p m . The b -distance generalizes the Hamming distance (b = 1) , and the symbol-pair distance (b = 2). While the Hamming and symbol-pair distances of all λ -constacyclic codes of length p s are completely determined, the general b -distance of such codes was left opened. In this paper, we provide a new technique to establish the b -distance of all λ -constacyclic codes of length p s , where 1 ≤ b ≤ ⌊ p 2 ⌋. As an application, all MDS b -symbol constacyclic codes of length p s over F p m are obtained. [ABSTRACT FROM AUTHOR]

The Z 2 s -additive codes are subgroups of Z 2 s n , and can be seen as a generalization of linear codes over Z 2 and Z 4. A Z 2 s -linear Hadamard code is a binary Hadamard code which is the Gray map image of a Z 2 s -additive code. A partial classification of these codes by using the dimension of the kernel is known. In this paper, we establish that some Z 2 s -linear Hadamard codes of length 2 t are equivalent, once t is fixed. This allows us to improve the known upper bounds for the number of such nonequivalent codes. Moreover, up to t = 11 , this new upper bound coincides with a known lower bound (based on the rank and dimension of the kernel). Finally, when we focus on s ∈ { 2 , 3 } , the full classification of the Z 2 s -linear Hadamard codes of length 2 t is established by giving the exact number of such codes. [ABSTRACT FROM AUTHOR]

Let R = GR (p e , m) [ u ] ∕ 〈 u k 〉 be a finite commutative ring for a prime p and any positive integers e , m and k. In this paper, we derive the explicit representation of cyclic codes over the ring R of length n , where n and p are coprime. We also discuss the dual of such cyclic codes over the ring R and give a sufficient condition for the codes to be self-dual. Moreover, we study quasi-cyclic codes of length k n and index k over the ring R , and obtain some good codes satisfying the bound given in Dougherty and Shiromoto (2000) over the ring Z 9 as an example. [ABSTRACT FROM AUTHOR]