16 resultados para FORCING CONJECTURE FOR GRAPHS

em Bulgarian Digital Mathematics Library at IMI-BAS


Relevância:

20.00% 20.00%

Publicador:

Resumo:

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.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

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.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

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.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

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.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

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.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

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.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

MSC 2010: 30C60

Relevância:

20.00% 20.00%

Publicador:

Resumo:

2000 Mathematics Subject Classification: 05C35.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

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

Relevância:

20.00% 20.00%

Publicador:

Resumo:

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

Relevância:

20.00% 20.00%

Publicador:

Resumo:

Асен Божилов, Недялко Ненов - Нека 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). В тази работа доказваме неравенството ...

Relevância:

20.00% 20.00%

Publicador:

Resumo:

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.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

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

Relevância:

20.00% 20.00%

Publicador:

Resumo:

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

Relevância:

20.00% 20.00%

Publicador:

Resumo:

2010 Mathematics Subject Classification: 05C38, 05C45.