Directed graph representation of half-rate additive codes over GF(4)

We show that (n, 2 ⁿ ) additive codes over GF(4) can be represented as directed graphs. This generalizes earlier results on self-dual additive codes over GF(4), which correspond to undirected graphs. Graph representation reduces the complexity of code classification, and enables us to classify additive (n, 2 ⁿ ) codes over GF(4) of length up to 7. From this we also derive classifications of isodual and formally self-dual codes. We introduce new constructions of circulant and bordered circulant directed graph codes, and show that these codes will always be isodual. A computer search of all such codes of length up to 26 reveals that these constructions produce many codes of high minimum distance. In particular, we find new near-extremal formally self-dual codes of length 11 and 13, and isodual codes of length 24, 25, and 26 with better minimum distance than the best known self-dual codes.     

Edge local complementation and equivalence of binary linear codes

Orbits of graphs under the operation edge local complementation (ELC) are defined. We show that the ELC orbit of a bipartite graph corresponds to the equivalence class of a binary linear code. The information sets and the minimum distance of a code can be derived from the corresponding ELC orbit. By extending earlier results on local complementation (LC) orbits, we classify the ELC orbits of all graphs on up to 12 vertices. We also give a new method for classifying binary linear codes, with running time comparable to the best known algorithm.     

New optimal [52, 26, 10] self-dual codes

We classify up to equivalence all optimal binary self-dual [52, 26, 10] codes having an automorphism of order 3 with 10 fixed points. We achieve this using a method for constructing self-dual codes via an automorphism of odd prime order. We study also codes with an automorphism of order 3 with 4 fixed points. Some of the constructed codes have new values β = 8, 9, and 12 for the parameter in their weight enumerator.     

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.     

Interlace polynomials: Enumeration, unimodality and connections to codes

The interlace polynomialq was introduced by Arratia, Bollobás, and Sorkin. It encodes many properties of the orbit of a graph under edge local complementation (ELC). The interlace polynomial Q, introduced by Aigner and van der Holst, similarly contains information about the orbit of a graph under local complementation (LC). We have previously classified LC and ELC orbits, and now give an enumeration of the corresponding interlace polynomials of all graphs of order up to 12. An enumeration of all circle graphs of order up to 12 is also given. We show that there exist graphs of all orders greater than 9 with interlace polynomials q whose coefficient sequences are non-unimodal, thereby disproving a conjecture by Arratia et al. We have verified that for graphs of order up to 12, all polynomials Q have unimodal coefficients. It has been shown that LC and ELC orbits of graphs correspond to equivalence classes of certain error-correcting codes and quantum states. We show that the properties of these codes and quantum states are related to properties of the associated interlace polynomials.     

Diagonally neighbour transitive codes and frequency permutation arrays

Constant composition codes have been proposed as suitable coding schemes to solve the narrow band and impulse noise problems associated with powerline communication, while at the same time maintaining a constant power output. In particular, a certain class of constant composition codes called frequency permutation arrays have been suggested as ideal, in some sense, for these purposes. In this paper we characterise a family of neighbour transitive codes in Hamming graphs in which frequency permutation arrays play a central rode. We also classify all the permutation codes generated by groups in this family.     

New Extremal Type II Codes Over ℤ4

Recently Type II codes over ℤ₄ have been introduced as self-dual codes containing the all-one vector with the property that all Euclidean weights are divisible by eight. The notion of extremality for the Euclidean weight has been also given. In this paper, we give two methods for constructing Type II codes over ℤ₄. By these methods, new extremal Type II codes of lengths 16, 24, 32 and 40 are constructed from weighing matrices.     

Random Walks on Directed Covers of Graphs

Directed covers of finite graphs are also known as periodic trees or trees with finitely many cone types. We expand the existing theory of directed covers of finite graphs to those of infinite graphs. While the lower growth rate still equals the branching number, upper and lower growth rates no longer coincide in general. Furthermore, the behavior of random walks on directed covers of infinite graphs is more subtle. We provide a classification in terms of recurrence and transience and point out that the critical random walk may be recurrent or transient. Our proof is based on the observation that recurrence of the random walk is equivalent to the almost sure extinction of an appropriate branching process. Two examples in random environment are provided: homesick random walk on infinite percolation clusters and random walk in random environment on directed covers. Furthermore, we calculate, under reasonable assumptions, the rate of escape with respect to suitable length functions and prove the existence of the asymptotic entropy providing an explicit formula which is also a new result for directed covers of finite graphs. In particular, the asymptotic entropy of random walks on directed covers of finite graphs is positive if and only if the random walk is transient.     

Construction of Extremal Type II Codes over ℤ4

In this paper, we give a pseudo-random method to construct extremal Type II codes overℤ₄ . As an application, we give a number of new extremal Type II codes of lengths 24, 32 and 40, constructed from some extremal doubly-even self-dual binary codes. The extremal Type II codes of length 24 have the property that the supports of the codewords of Hamming weight 10 form 5−(24,10,36) designs. It is also shown that every extremal doubly-even self-dual binary code of length 32 can be considered as the residual code of an extremal Type II code over ℤ₄.     

Equivariant Reidemeister torsion on symmetric spaces

We calculate explicitly the equivariant Ray-Singer torsion for all symmetric spaces of compact type with respect to the action of . We show that it equals zero except for the odd-dimensional Gra?mannians and the space . As a corollary, we classify up to diffeomorphism all isometries of these spaces which are homotopic to the identity; also, we classify their quotients by finite group actions up to homeomorphism. Received: 31 May 1995 / In revised form: 9 January 1996     

Optimal Ternary Linear Rate 1/2 Codes

In this paper, we classify all optimal linear[n, n/2] codes up to length 12. We show that thereis a unique optimal [10, 5, 5] code up to equivalence.     

Globally Linked Pairs of Vertices in Equivalent Realizations of Graphs

A two-dimensional framework (G,p) is a graph G = (V,E) together with a map p: V → ℝ². We view (G,p) as a straight line realization of G in ℝ². Two realizations of G are equivalent if the corresponding edges in the two frameworks have the same length. A pair of vertices {u,v} is globally linked in G if %and for all equivalent frameworks (G,q), the distance between the points corresponding to u and v is the same in all pairs of equivalent generic realizations of G. The graph G is globally rigid if all of its pairs of vertices are globally linked. We extend the characterization of globally rigid graphs given by the first two authors [13] by characterizing globally linked pairs in M-connected graphs, an important family of rigid graphs. As a byproduct we simplify the proof of a result of Connelly [6] which is a key step in the characterization of globally rigid graphs. We also determine the number of distinct realizations of an M-connected graph, each of which is equivalent to a given generic realization. Bounds on this number for minimally rigid graphs were obtained by Borcea and Streinu in [3].     

On the classification of the extremal self-dual codes over small fields with 2-transitive automorphism groups

There are seven binary extremal self-dual doubly-even codes which are known to have a 2-transitive automorphism group. Using representation theoretical methods we show that there are no other such codes, except possibly for length n = 1024. We also classify all extremal ternary self-dual and quaternary Hermitian self-dual codes.     

Dominated error correcting codes with distance two

We study the hamiltonicity of certain graphs obtained from the hypercube as a means of producing a binary code of distance two and length n, whose codewords are ordered so that for each two consecutive codewords, one dominates the other. One vector dominates the other, if and only if, in all the positions where one of them has a zero, the other has a zero too. These dominated codes have applications in group testing for consecutive defectives. We also determine when the vectors can be ordered so that every two consecutive vectors have the domination property, and are at distance two; this is a natural generalization of Gray codes. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 294–302, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10012     

Codes from the incidence matrices of graphs on 3-sets

We examine the p-ary linear codes from incidence matrices of the three uniform subset graphs with vertex set the set of subsets of size 3 of a set of size n, with adjacency defined by two vertices as 3-sets being adjacent if they have zero, one or two elements in common, respectively. All the main parameters of the codes and the nature of the minimum words are obtained, and it is shown that the codes can be used for full error-correction by permutation decoding. We examine also the binary codes of the line graphs of these graphs.     

On the structure of hereditary classes of graphs

A class of graphs is hereditary if it is closed under taking induced subgraphs. Classes associated with graph representations have “composition sequences” and we show that this concept is equivalent to a notion of “amalgamation” which generalizes disjoint union of graphs. We also discuss how general hereditary classes of graphs are built up from representation classes.     

Binary Codes of Strongly Regular Graphs

For strongly regular graphs ith adjacency matrix A, we look at the binary codes generated by A and A + I. We determine these codes for some families of graphs, e pay attention to the relation beteen the codes of switching equivalent graphs and, ith the exception of two parameter sets, we generate by computer the codes of all knon strongly regular graphs on fewer than 45 vertices.     

Topological groups and recurrence of quasi transitive graphs

We present all steps which are necessary in order to classify all locally finite, infinite graphs which carry a quasi transitive random walk that is recurrent. Some new and/or simpler proofs are given. Most of them rely on the fact that autmomorphism groups of locally finite graphs are locally compact with respect to the topology of pointwise convergence—this allows the use of integration on these groups. Conferenza tenuta il 28 novembre 1994     

Ternary codes from the strongly regular (45, 12, 3, 3) graphs and orbit matrices of 2-(45, 12, 3) designs

The enumeration of strongly regular graphs with parameters (45, 12, 3, 3) has been completed, and it is known that there are 78 non-isomorphic strongly regular (45, 12, 3, 3) graphs. A strongly regular graph with these parameters is a symmetric (45, 12, 3) design having a polarity with no absolute points. In this paper we examine the ternary codes obtained from the adjacency (resp. incidence) matrices of these graphs (resp. designs), and those of their corresponding derived and residual designs. Further, we give a generalization of a result of Harada and Tonchev on the construction of non-binary self-orthogonal codes from orbit matrices of block designs under an action of a fixed-point-free automorphism of prime order. Using the generalized result we present a complete classification of self-orthogonal ternary codes of lengths 12, 13, 14, and 15, obtained from non-fixed parts of orbit matrices of symmetric (45, 12, 3) designs admitting an automorphism of order 3. Several of the codes obtained are optimal or near optimal for the given length and dimension. We show in addition that the dual codes of the strongly regular (45, 12, 3, 3) graphs admit majority logic decoding.     

On the minimum distance graph of an extended Preparata code

The minimum distance graph of an extended Preparata code P(m) has vertices corresponding to codewords and edges corresponding to pairs of codewords that are distance 6 apart. The clique structure of this graph is investigated and it is established that the minimum distance graphs of two extended Preparata codes are isomorphic if and only if the codes are equivalent.