On the Vertex Separation of Cactus Graphs

This paper is part of a work in progress whose goal is to construct a fast, practical algorithm for the vertex separation (VS) of cactus graphs. We prove a \main theorem for cacti", a necessary and sufficient condition for the VS of a cactus graph being k. Further, we investigate the ensuing ramifications that prevent the construction of an algorithm based on that theorem only.

On Graph-Based Cryptography and Symbolic Computations

We have been investigating the cryptographical properties of in nite families of simple graphs of large girth with the special colouring of vertices during the last 10 years. Such families can be used for the development of cryptographical algorithms (on symmetric or public key modes) and turbocodes in error correction theory. Only few families of simple graphs of large unbounded girth and arbitrarily large degree are known. The paper is devoted to the more general theory of directed graphs of large girth and their cryptographical applications. It contains new explicit algebraic constructions of in finite families of such graphs. We show that they can be used for the implementation of secure and very fast symmetric encryption algorithms. The symbolic computations technique allow us to create a public key mode for the encryption scheme based on algebraic graphs.

Some MDS Codes over Gf(64) Connected with the Binary Doubly-Even [72,36,16] Code

* The author is supported by a Return Fellowship from the Alexander von Humboldt Foundation.

On the Vertex Separation of Maximal Outerplanar Graphs

We investigate the NP-complete problem Vertex Separation (VS) on Maximal Outerplanar Graphs (mops). We formulate and prove a “main theorem for mops”, a necessary and sufficient condition for the vertex separation of a mop being k. The main theorem reduces the vertex separation of mops to a special kind of stretchability, one that we call affixability, of submops.

New Binary $[70,35,12]$ Self-Dual and Binary $[72,36,12]$ Self-Dual Doubly-Even Codes

∗ This work was supported in part by the Bulgarian NSF under Grant MM-901/99

New Symmetric (61,16,4) Designs Invariant Under the Dihedral Group of Order 10

∗ This work has been partially supported by the Bulgarian NSF under Contract No. I-506/1995.

Learning Technology in Scheduling Based on the Mixed Graphs

We propose the adaptive algorithm for solving a set of similar scheduling problems using learning technology. It is devised to combine the merits of an exact algorithm based on the mixed graph model and heuristics oriented on the real-world scheduling problems. The former may ensure high quality of the solution by means of an implicit exhausting enumeration of the feasible schedules. The latter may be developed for certain type of problems using their peculiarities. The main idea of the learning technology is to produce effective (in performance measure) and efficient (in computational time) heuristics by adapting local decisions for the scheduling problems under consideration. Adaptation is realized at the stage of learning while solving a set of sample scheduling problems using a branch-and-bound algorithm and structuring knowledge using pattern recognition apparatus.

On Multi-Dimensional Random Walk Models Approximating Symmetric Space-Fractional Diffusion Processes

Mathematics Subject Classification: 26A33, 47B06, 47G30, 60G50, 60G52, 60G60.

Conjugate Compositions in Even-Dimensional Affinely Connected Spaces without a Torsion

Let in even-dimensional a±nely connected space without a torsion A2m be given a composition Xm£Xm by the affinor a¯ ®. The affinor b¯ ®, determined with the help of the eigen-vectors of the matrix (a¯ ®), de¯nes the second composition Ym £ Y m. Conjugate compositions are introduced by the condition: the a±nors of any of both compositions transform the vectors from the one position of the composition, generated by the other a±nor, in the vectors from the another its position. It is proved that the compositions de¯ne by a±nors a¯ ® and b¯ ® are conjugate. It is proved also that if the composition Xm£Xm is Cartesian and composition Ym£Y m is Cartesian or chebyshevian, or geodesic than the space A2m is affine.

Natural Connections with Totally Skew-Symmetric Torsion on Manifolds with Norden-Type Metrics

This paper is a survey of results obtained by the authors on the geometry of connections with totally skew-symmetric torsion on the following manifolds: almost complex manifolds with Norden metric, almost contact manifolds with B-metric and almost hypercomplex manifolds with Hermitian and anti-Hermitian metric.

On Extremal Binary Doubly-Even Self-Dual Codes of Length 88*

In this paper we present 35 new extremal binary self-dual doubly-even codes of length 88. Their inequivalence is established by invariants. Moreover, a construction of a binary self-dual [88, 44, 16] code, having an automorphism of order 21, is given.

The Eccentric Connectivity Polynomial of some Graph Operations

The eccentric connectivity index of a graph G, ξ^C, was proposed by Sharma, Goswami and Madan. It is defined as ξ^C(G) = ∑ u ∈ V(G) degG(u)εG(u), where degG(u) denotes the degree of the vertex x in G and εG(u) = Max{d(u, x) | x ∈ V (G)}. The eccentric connectivity polynomial is a polynomial version of this topological index. In this paper, exact formulas for the eccentric connectivity polynomial of Cartesian product, symmetric difference, disjunction and join of graphs are presented.

Numerical Solution of Fractional Diffusion-Wave Equation with two Space Variables by Matrix Method

Mathematics Subject Classi¯cation 2010: 26A33, 65D25, 65M06, 65Z05.

Sequences of Maximal Degree Vertices in Graphs

2000 Mathematics Subject Classification: 05C35.

Direct and Inverse Spectral Problems for (2N + 1)-Diagonal, Complex, Symmetric, Non-Hermitian Matrices

2000 Mathematics Subject Classification: 42C05.