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 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.

On some Results Related to Köthe's Conjecture

The Köthe conjecture states that if a ring R has no nonzero nil ideals then R has no nonzero nil one-sided ideals. Although for more than 70 years significant progress has been made, it is still open in general. In this paper we survey some results related to the Köthe conjecture as well as some equivalent problems.

Generalization of a Conjecture in the Geometry of Polynomials

In this paper we survey work on and around the following conjecture, which was first stated about 45 years ago: If all the zeros of an algebraic polynomial p (of degree n ≥ 2) lie in a disk with radius r, then, for each zero z1 of p, the disk with center z1 and radius r contains at least one zero of the derivative p′ . Until now, this conjecture has been proved for n ≤ 8 only. We also put the conjecture in a more general framework involving higher order derivatives and sets defined by the zeros of the polynomials.

Toward Clemens' Conjecture in Degrees between 10 and 24

1 Supported in part by the Norwegian Research Council for Science and the Humanities. It is a pleasure for this author to thank the Department of Mathematics of the University of Sofia for organizing the remarkable conference in Zlatograd during the period August 28-September 2, 1995. It is also a pleasure to thank the M.I.T. Department of Mathematics for its hospitality from January 1 to July 31, 1993, when this work was started. 2Supported in part by NSF grant 9400918-DMS.

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.

Hilbert-Smith Conjecture for K - Quasiconformal Groups

MSC 2010: 30C60

Sequences of Maximal Degree Vertices in Graphs

2000 Mathematics Subject Classification: 05C35.

Remarks on the Nagata Conjecture

2000 Mathematics Subject Classification: 14C20, 14E25, 14J26.

A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs

ACM Computing Classification System (1998): G.2.2.

An Inequality for Generalized Chromatic Graphs

Асен Божилов, Недялко Ненов - Нека G е n-върхов граф и редицата от степените на върховете му е d1, d2, . . . , dn, а V(G) е множеството от върховете на G. Степента на върха v бележим с d(v). Най-малкото естествено число r, за което V(G) има r-разлагане V(G) = V1 ∪ V2 ∪ · · · ∪ Vr, Vi ∩ Vj = ∅, , i 6 = j такова, че d(v) ≤ n − |Vi|, ∀v ∈ Vi, i = 1, 2, . . . , r е означено с ϕ(G). В тази работа доказваме неравенството ...

The Wiener, Eccentric Connectivity and Zagreb Indices of the Hierarchical Product of Graphs

Let G1 = (V1, E1) and G2 = (V2, E2) be two graphs having a distinguished or root vertex, labeled 0. The hierarchical product G2 ⊓ G1 of G2 and G1 is a graph with vertex set V2 × V1. Two vertices y2y1 and x2x1 are adjacent if and only if y1x1 ∈ E1 and y2 = x2; or y2x2 ∈ E2 and y1 = x1 = 0. In this paper, the Wiener, eccentric connectivity and Zagreb indices of this new operation of graphs are computed. As an application, these topological indices for a class of alkanes are computed. ACM Computing Classification System (1998): G.2.2, G.2.3.

Smale's Conjecture on Mean Values of Polynomials and Electrostatics

2000 Mathematics Subject Classification: Primary 30C10, 30C15, 31B35.

A Note About the Nowicki Conjecture on Weitzenböck Derivations

2000 Mathematics Subject Classification: 13N15, 13A50, 16W25.

Dirac type condition and Hamiltonian graphs

2010 Mathematics Subject Classification: 05C38, 05C45.