On a class of binary linear completely transitive codes with arbitrary covering radius

An infinite class of new binary linear completely transitive (and so, completely regular) codes is given. The covering radius of these codes is growing with the length of the code. In particular, for any integer ρ≥2, there exist two codes in the constructed class with d=3, covering radius ρ and lengths and , respectively. The corresponding distance-transitive graphs, which can be defined as coset graphs of these completely transitive codes are described.     

Bounds on Codes Derived by Counting Components in Varshamov Graphs

We are interested in improving the Varshamov bound for finite values of length n and minimum distance d. We employ a counting lemma to this end which we find particularly useful in relation to Varshamov graphs. Since a Varshamov graph consists of components corresponding to low weight vectors in the cosets of a code it is a useful tool when trying to improve the estimates involved in the Varshamov bound. We consider how the graph can be iteratively constructed and using our observations are able to achieve a reduction in the over-counting which occurs. This tightens the lower bound for any choice of parameters n, k, d or q and is not dependent on information such as the weight distribution of a code. This work is taken from the author’s thesis [10]     

Novel evolutionary models and applications to sequence alignment problems

In this paper, we present a novel graph-theoretical approach for representing a wide variety of sequence analysis problems within a single model. The model allows incorporation of the operations “insertion”, “deletion”, and “substitution”, and various parameters such as relative distances and weights. Conceptually, we refer the problem as the minimum weight common mutated sequence (MWCMS) problem. The MWCMS model has many applications including multiple sequence alignment problem, the phylogenetic analysis, the DNA sequencing problem, and sequence comparison problem, which encompass a core set of very difficult problems in computational biology. Thus the model presented in this paper lays out a mathematical modeling framework that allows one to investigate theoretical and computational issues, and to forge new advances for these distinct, but related problems. Through the introduction of supernodes, and the multi-layer supergraph, we proved that MWCMS is -complete. Furthermore, it was shown that a conflict graph derived from the multi-layer supergraph has the property that a solution to the associated node-packing problem of the conflict graph corresponds to a solution of the MWCMS problem. In this case, we proved that when the number of input sequences is a constant, MWCMS is polynomial-time solvable. We also demonstrated that some well-known combinatorial problems can be viewed as special cases of the MWCMS problem. In particular, we presented theoretical results implied by the MWCMS theory for the minimum weight supersequence problem, the minimum weight superstring problem, and the longest common subsequence problem. Two integer programming formulations were presented and a simple yet elegant decomposition heuristic was introduced. The integer programming instances have proven to be computationally intensive. Consequently, research involving simultaneous column and row generation and parallel computing will be explored. The heuristic algorithm, introduced herein for multiple sequence alignment, overcomes the order-dependent drawbacks of many of the existing algorithms, and is capable of returning good sequence alignments within reasonable computational time. It is able to return the optimal alignment for multiple sequences of length less than 1500 base pairs within 30 minutes. Its algorithmic decomposition nature lends itself naturally for parallel distributed computing, and we continue to explore its flexibility and scalability in a massive parallel environment.     

图同构的必要条件

结合图对应的邻接矩阵,利用矩阵的秩和矩阵的合同关系,得到了图同构的一个必要条件;然后给出了图同构的一个理论判断的算法．     

一类半对称图的构造

称一个有限简单无向图X是半对称图,如果图X是正则的且边传递但非点传递.主要利用仿射几何构造了一类2p~n阶连通p~3。度的半对称图的无限族,其中p≥n≥8.     

Some fixed point results on a metric space with a graph

Combining some branches is a typical activity in different fields of science, especially in mathematics. Naturally, it is notable in fixed point theory. Over the past few decades, there have been a lot of activity in fixed point theory and another branches in mathematics such differential equations, geometry and algebraic topology. In 2006, Espinola and Kirk made a useful contribution on combining fixed point theory and graph theory. Recently, Reich and Zaslavski studied a new inexact iterative scheme for fixed points of contractive and nonexpansive multifunctions. In this paper, by using main idea of their work and the idea of combining fixed point theory and graph theory, we present some iterative scheme results for G-contractive and G-nonexpansive mappings on graphs.     

Normal systems over ANR’s, rigid embeddings and nonseparable absorbing sets

Most of results of Bestvina and Mogilski [Characterizing certain incomplete infinite-di-mensional absolute retracts. Michigan Math. J., 33, 291-313 (1986)] on strong Z-sets in ANR's and absorbing sets is generalized to nonseparable case. It is shown that if an ANR X is locally homotopy dense embeddable in infinite-dimensional Hilbert manifolds and w(U ) = w(X ) (where "w"is the topological weight) for each open nonempty subset U of X , then X itself is homotopy dense embeddable in a Hilbert manifold. It is also demonstrated that whenever X is an AR, its weak product W (X, ) = {(x n ) ∞ n=1 ∈ X ω : x n = for almost all n} is homeomorphic to a pre-Hilbert space E with E ～ = ΣE. An intrinsic characterization of manifolds modelled on such pre-Hilbert spaces is given.