On spanning connected graphs

A k-containerC(u,v) of G between u and v is a set of k internally disjoint paths between u and v. A k-container C(u,v) of G is a k^*-container if the set of the vertices of all the paths in C(u,v) contains all the vertices of G. A graph G is k^*-connected if there exists a k^*-container between any two distinct vertices. Therefore, a graph is 1^*-connected (respectively, 2^*-connected) if and only if it is hamiltonian connected (respectively, hamiltonian). In this paper, a classical theorem of Ore, providing sufficient conditional for a graph to be hamiltonian (respectively, hamiltonian connected), is generalized to k^*-connected graphs.     

Affine nonsystematic codes

A perfect binary code C of length n = 2 ^k ? 1 is called affine systematic if there exists a k-dimensional subspace of {0, 1} ⁿ such that the intersection of C and each coset with respect to this subspace is a singleton; otherwise C is called affine nonsystematic. In this article we construct affine nonsystematic codes.     

Two-weight ternary codes and the equation y2 = 4 × 3a + 13

This paper determines the parameters of all two-weight ternary codes C with the property that the minimum weight in the dual code C^⊥ is at least 4. This yields a characterization of uniformly packed ternary [n, k, 4] codes. The proof rests on finding all integer solutions of the equation y² = 4 × 3^a + 13.     

Completely simple codes

A code X is said to be completely simple if the kernel of the syntactic monoid of X ^? is a completely simple semigroup. This class of codes is a common generalization of two important classes of codes, that is, thin codes and group codes, and has remarkable algebraic and combinatorial properties. In this paper, we give systematic characterizations of completely simple codes and, in particular, show that many fundamental properties of thin codes are preserved in this generalization.     

A criterion for polynomial growth of a-free two-peak posets of tame prinjective type *

It is well known from the results of L, A. Nazarova and A. G. Zavadskij [18], [19], see also [25, Chapter 15], that a poset J with one maximal element is of tame prinjective type and of polynomial growth if and only if J does not contain neither any of the Nazarova's hypercritical posets (1,1,1,1,1)^*, (1,1,1,2)^*,(2,2,3)^*, (1,3,4)^*,(W,5)^*,(1,2,6)^* nor the Nazarova-Zavadskij poset (NZ)^* (see Table 1 below). In the present paper we extend this result to a class of posets with two maximal elements. We show that Ã-free poset with two maximal elements is of tame representation type and of polynomial growth if and only if the Tits quadratic form q^s → Z (see (1.7) below) associated with J is weakly non-negative and J does not contain any of the six posets listed in Table 1 as a peak subposet.     

An Enumeration of Binary Self-Dual Codes of Length 32

A binary self-dual code of length 2k is a (2k, k) binary linear code C with the property that every pair of codewords in C are orthogonal. Two self-dual codes, C ₁ and C ₂, are equivalent if and only if there is a permutation of the coordinates of C ₁ that takes C ₁ into C ₂. The automorphism group of a binary code C is the set of all permutations of the coordinates of C that takes C into itself.The main topic of this paper is the enumeration of inequivalent binary self-dual codes. We have developed algorithms that will take lists of inequivalent small codes and produce lists of larger codes where each inequivalent code occurs only a few times. We have defined a canonical form for codes that allowed us to eliminate the overenumeration. So we have lists of inequivalent binary self-dual codes of length up to 32. The enumeration of the length 32 codes is new. Our algorithm also finds the size of the automorphism group so that we can compute the number of distinct binary self-dual codes for a specific length. This number can also be found by counting and matches our total.     

On extremely transitive extended perfect codes

We prove that, for every n = 2 ^k with k ≥ 4, there exist nonequivalent extremely transitive extended perfect codes. A transitive extended perfect code we call extremely transitive if the perfect code obtained from this code by puncturing any coordinate position is not transitive. The classification is given for all extended perfect codes of length 16.     

Nonexistence of near-extremal formally self-dual even codes of length divisible by 8

It is a well-known fact that if C is an [n,k,d] formally self-dual even code with n>30, then d?2[n/8]. A formally self-dual (f.s.d.) even code with d=2[n/8] is called near-extremal. Kim and Pless [A note on formally self-dual even codes of length divisible by 8, Finite Fields Appl., available online 13 October 2005.] conjecture that there does not exist a near-extremal f.s.d. (not Type II) code of length n?48 with 8|n. In this paper, we prove that if n?72 and 8|n, then there is no near-extremal f.s.d. even code. This result comes from the negative coefficients of weight enumerators. In addition, we introduce shadow transform in near-extremal f.s.d. even codes. Using this we present some results about the nonexistence of near-extremal f.s.d. even codes with n=48,64.     

On the spanning connectivity of graphs

A k-containerC(u,v) of G between u and v is a set of k internally disjoint paths between u and v. A k-container C(u,v) of G is a k^*-container if it contains all vertices of G. A graph G is k^*-connected if there exists a k^*-container between any two distinct vertices. The spanning connectivity of G, κ^*(G), is defined to be the largest integer k such that G is w^*-connected for all 1?w?k if G is a 1^*-connected graph. In this paper, we prove that κ^*(G)?2δ(G)-n(G)+2 if (n(G)/2)+1?δ(G)?n(G)-2. Furthermore, we prove that κ^*(G-T)?2δ(G)-n(G)+2-|T| if T is a vertex subset with |T|?2δ(G)-n(G)-1.     

Neighbour transitivity on codes in Hamming graphs

We consider a code to be a subset of the vertex set of a Hamming graph. In this setting a neighbour of the code is a vertex which differs in exactly one entry from some codeword. This paper examines codes with the property that some group of automorphisms acts transitively on the set of neighbours of the code. We call these codes neighbour transitive. We obtain sufficient conditions for a neighbour transitive group to fix the code setwise. Moreover, we construct an infinite family of neighbour transitive codes, with minimum distance δ = 4, where this is not the case. That is to say, knowledge of even the complete set of code neighbours does not determine the code.     

Über die Wurzelschranke für das Minimalgewicht von codes

Let d be the minimum distance of an (n, k) code $\text{C}$, invariant under an abelian group acting transitively on the basis of the ambient space over a field F with char F × n. Assume that $\text{C}$ contains the repetition code, that dim($\text{C}$ ∏ $\text{C}$^⊥) = k ? 1 and that the supports of the minimal weight vectors of $\text{C}$ form a 2-design. Then d² ? d + 1 ? n with equality if and only if the design is a projective plane of order d ? 1. The case d² ? d + 1 = n can often be excluded with Hall's multiplier theorem on projective planes, a theorem which follows easily from the tools developed in this paper Moreover, if d² ? d + 1 > n and F = GF(2) then (d ? 1)² ? n. Examples are the generalized quadratic residue codes.     

Classifying simple closed curve pairs in the 2-sphere and a generalization of the Schoenflies theorem

A classification theory is developed for pairs of simple closed curves (A,B) in the sphere S², assuming that A∩B has finitely many components. Such a pair of simple closed curves is called an SCC-pair, and two SCC-pairs (A,B) and (A^′,B^′) are equivalent if there is a homeomorphism from S² to itself sending A to A^′ and B to B^′. The simple cases where A and B coincide or A and B are disjoint are easily handled. The component code is defined to provide a classification of all of the other possibilities. The component code is not uniquely determined for a given SCC-pair, but it is straightforward that it is an invariant; i.e., that if (A,B) and (A^′,B^′) are equivalent and C is a component code for (A,B), then C is a component code for (A^′,B^′) as well. It is proved that the component code is a classifying invariant in the sense that if two SCC-pairs have a component code in common, then the SCC-pairs are equivalent. Furthermore code transformations on component codes are defined so that if one component code is known for a particular SCC-pair, then all other component codes for the SCC-pair can be determined via code transformations. This provides a notion of equivalence for component codes; specifically, two component codes are equivalent if there is a code transformation mapping one to the other. The main result of the paper asserts that if C and C^′ are component codes for SCC-pairs (A,B) and (A^′,B^′), respectively, then (A,B) and (A^′,B^′) are equivalent if and only if C and C^′ are equivalent. Finally, a generalization of the Schoenflies theorem to SCC-pairs is presented.     

On deep holes of standard Reed-Solomon codes

Determining deep holes is an important open problem in decoding Reed-Solomon codes. It is well known that the received word is trivially a deep hole if the degree of its Lagrange interpolation polynomial equals the dimension of the Reed-Solomon code. For the standard Reed-Solomon codes [p-1, k]p with p a prime, Cheng and Murray conjectured in 2007 that there is no other deep holes except the trivial ones. In this paper, we show that this conjecture is not true. In fact, we find a new class of deep holes for standard Reed-Solomon codes [q-1, k]q with q a power of the prime p. Let q≥4 and 2≤k≤q-2. We show that the received word u is a deep hole if its Lagrange interpolation polynomial is the sum of monomial of degree q-2 and a polynomial of degree at most k-1. So there are at least 2(q-1)qk deep holes if k q-3.     

Basic sequences and norming subspaces in non-quasi-reflexive Banach spaces

A Banach spaceX is non-quasi-reflexive (i.e. dimX ^**/X=∞) if and only if it contains a basic sequence spanning a non-quasi-reflexive subspace. In fact, this basic sequence can be chosen to be non-k-boundedly complete for allk. A basic sequence which is non-k-shrinking for allk exists inX if and only ifX ^* contains a norming subspace of infinite codimension. This need not occur even ifX is non-quasi-reflexive. Every norming subspace ofX ^* has finite codimension if and only if for every normingM inX ^*, everyM-closedY inX,M∩Y ^T is norming overX/Y. This solves a problem due to Schäffer [19].     

A new upper bound on the cyclic chromatic number

A cyclic coloring of a plane graph is a vertex coloring such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a graph is its cyclic chromatic number χ^c. Let Δ^* be the maximum face degree of a graph. There exist plane graphs with χ^c = ?3/2 Δ^*?. Ore and Plummer [ 5 ] proved that χ^c ≤ 2, Δ^*, which bound was improved to ?9/5, Δ^*? by Borodin, Sanders, and Zhao [ 1 ], and to ?5/3,Δ^*? by Sanders and Zhao [ 7 ]. We introduce a new parameter k^*, which is the maximum number of vertices that two faces of a graph can have in common, and prove that χ^c ≤ max {Δ^* + 3,k^* + 2, Δ^* + 14, 3, k^* + 6, 18}, and if Δ^* ≥ 4 and k^* ≥ 4, then χ^c ≤ Δ^* + 3,k^* + 2. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Quasi-cyclic codes with cyclic constituent codes

Ling and Solé [S. Ling, P. Solé, On the algebraic structure of quasi-cyclic codes I: Finite fields, IEEE Trans. Inform. Theory 47 (2001) 2751–2760] showed that every quasi-cyclic code C is constructed from shorter linear codes which are called the constituent codes of C. Given a quasi-cyclic code C of length ℓm and index ℓ with m being pairwise coprime to ℓ and the order of the field C is over, if all its constituent codes are cyclic with their zeroes having full multiplicity, C is then shown to be equivalent to a cyclic code whose zeroes with their multiplicities are fully described in terms of the nonzeroes of the cyclic constituent codes. The general transformation to obtain the above-mentioned equivalent cyclic code is also explicitly given. The approach adopted here follows the approach used by A.M.A. Natividad [A.M.A. Natividad, PhD thesis, Department of Mathematics, University of Philippines Diliman, The Philippines, 2004] and uses the generalized discrete Fourier transform on the algebraic structure of the class of quasi-cyclic codes developed by Ling and Solé [S. Ling, P. Solé, On the algebraic structure of quasi-cyclic codes I: Finite fields, IEEE Trans. Inform. Theory 47 (2001) 2751–2760].     

Intersection of Isomorphic Linear Codes

Given an (n, k) linear code over GF(q), the intersection of with a codeπ( ), whereπS_n, is an (n, k₁) code, where max{0, 2k−n}k₁k. The intersection problem is to determine which integers in this range are attainable for a given code . We show that, depending on the structure of the generator matrix of the code, some of the values in this range are attainable. As a consequence we give a complete solution to the intersection problem for most of the interesting linear codes, e.g. cyclic codes, Reed–Muller codes, and most MDS codes.     

Binary codes and partial permutation decoding sets from the odd graphs

For k ≥ 1, the odd graph denoted by O(k), is the graph with the vertex-set Ω^{k}, the set of all k-subsets of Ω = {1, 2, …, 2k +1}, and any two of its vertices u and v constitute an edge [u, v] if and only if u ∩ v = /0. In this paper the binary code generated by the adjacency matrix of O(k) is studied. The automorphism group of the code is determined, and by identifying a suitable information set, a 2-PD-set of the order of k ⁴ is determined. Lastly, the relationship between the dual code from O(k) and the code from its graph-theoretical complement $\overline {O(k)} $ , is investigated.     

On the binary codes with parameters of triply-shortened 1-perfect codes

We study properties of binary codes with parameters close to the parameters of 1-perfect codes. An arbitrary binary (n?=?2 ^m ? 3, 2 ^n-m-1, 4) code C, i.e., a code with parameters of a triply-shortened extended Hamming code, is a cell of an equitable partition of the n-cube into six cells. An arbitrary binary (n?=?2 ^m ? 4, 2 ^n-m , 3) code D, i.e., a code with parameters of a triply-shortened Hamming code, is a cell of an equitable family (but not a partition) with six cells. As a corollary, the codes C and D are completely semiregular; i.e., the weight distribution of such codes depends only on the minimal and maximal codeword weights and the code parameters. Moreover, if D is self-complementary, then it is completely regular. As an intermediate result, we prove, in terms of distance distributions, a general criterion for a partition of the vertices of a graph (from rather general class of graphs, including the distance-regular graphs) to be equitable.     

Lacunary interpolation by quartic splines on uniform meshes

The interpolation of a discrete set of data on the interval [0, 1], representing the first and the second derivatives (except at 0) of a smooth function f is investigated via quartic C²-splines. Error bounds in the uniform norm for ∥s⁽ⁱ⁾ − f⁽ⁱ⁾∥, i=0(1)2, if f ∈ C^l[0, 1], l=3, 5 and ⁽³⁾ ∈ BV[0, 1], together with computational examples will also be presented.