On the Vertex Folkman Numbers Fv(2,...,2;q)

2000 Mathematics Subject Classification: 05C55.

On a Class of Vertex Folkman Numbers

Let a1 , . . . , ar, be positive integers, i=1 ... r, m = ∑(ai − 1) + 1 and p = max{a1 , . . . , ar }. For a graph G the symbol G → (a1 , . . . , ar ) means that in every r-coloring of the vertices of G there exists a monochromatic ai -clique of color i for some i ∈ {1, . . . , r}. In this paper we consider the vertex Folkman numbers F (a1 , . . . , ar ; m − 1) = min |V (G)| : G → (a1 , . . . , ar ) and Km−1 ⊂ G} We prove that F (a1 , . . . , ar ; m − 1) = m + 6, if p = 3 and m ≧ 6 (Theorem 3) and F (a1 , . . . , ar ; m − 1) = m + 7, if p = 4 and m ≧ 6 (Theorem 4).

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 the 3-Colouring Vertex Folkman Number F(2,2,4)

In this note we prove that F (2, 2, 4) = 13.

A Metaheuristic Approach to Solving the Generalized Vertex Cover Problem

AMS Subj. Classification: 90C27, 05C85, 90C59

New Upper Bound for the Edge Folkman Number Fe(3,5;13)

2000 Mathematics Subject Classification: 05C55.

Approximation Classes for Adaptive Methods

* This work has been supported by the Office of Naval Research Contract Nr. N0014-91-J1343, the Army Research Office Contract Nr. DAAD 19-02-1-0028, the National Science Foundation grants DMS-0221642 and DMS-0200665, the Deutsche Forschungsgemeinschaft grant SFB 401, the IHP Network “Breaking Complexity” funded by the European Commission and the Alexan- der von Humboldt Foundation.

Generating More Boundary Elements of Subset Projections

Composition problem is considered for partition constrained vertex subsets of n dimensional unit cube E^n . Generating numerical characteristics of E^n subsets partitions is considered by means of the same characteristics in 1 − n dimensional unit cube, and construction of corresponding subsets is given for a special particular case. Using pairs of lower layer characteristic vectors for E^(1-n) more characteristic vectors for E^n are composed which are boundary from one side, and which take part in practical recognition of validness of a given candidate vector of partitions.

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.

Sequences of Maximal Degree Vertices in Graphs

2000 Mathematics Subject Classification: 05C35.

Singular Solutions with Exponential Growth for the (3+1)-D Wave Equation

Недю И. Попиванов, Тодор П. Попов, Рудолф Шерер - Разглеждат се четиримерни гранични задачи за нехомогенното вълново уравнение. Те са предложени от М. Протер като многомерни аналози на задачата на Дарбу в равнината. Известно е, че единственото обобщено решение може да има силна степенна особеност само в една гранична точка. Тази сингулярност е изолирана във върха на характеристичния конус и не се разпространява по конуса. Друг аспект на проблема е, че задачата не е фредхолмова, тъй като има безкрайномерно коядро. Предишни резултати сочат, че решението може да има най-много експоненциален ръст, но оставят открит въпроса дали наистина съществуват такива решения. Показваме, че отговора на този въпрос е положителен и строим обобщено решение на задачата на Протер с експоноциална особеност.

A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs

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

A New Method for Computing the Eccentric Connectivity Index of Fullerenes

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

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). В тази работа доказваме неравенството ...