**Seminar on
Applied Mathematics**

**PROGRAM**

Matematički fakultet

Fakultet organizacionih nauka

JUPIM

MI SANU, Knez Mihailova 36, sala 305

**
**

**
Utorak, 18.03.2008. u 14:15, sala 305, MI BG:
**

**
Nebojsa Gvozdenovic, Ekonomski fakultet, Subotica
APPROXIMATING THE STABILITY NUMBER AND THE CHROMATIC
NUMBER OF A GRAPH VIA SEMIDEFINITE PROGRAMMING
**

**
Abstract: We introduce a special operator $\Psi$ which maps upper
bounds for the stability number to lower bounds for the chromatic
number. As an application, we prove that there is no polynomial
time computable graph parameter nested between the fractional
chromatic and the chromatic number of a graph, unless P=NP.
**

**
Utorak, 25.03.2008. u 14:15, sala 305, MI BG:
**

**
Tatjana Davidovic, Dragos Cvetkovic, Matematicki institut SANU,
Beograd
CHARACTERIZATION OF MULTIPROCESSOR INTERCONNECTION
NETWORKS USING GRAPH THEORY
**

**
Abstract: Homogeneous multiprocessor systems are usually modelled
by undirected graphs. Vertices of these graphs represent the
processors, while edges denote the connection links between
adjacent processors. Let $G$ be a graph with diameter $D$, maximum
vertex degree $\Delta$, the largest eigenvalue $\lambda_1$ and $m$
distinct eigenvalues. The products $m\Delta$ and $(D+1)\lambda_1$
are called the tightness of $G$ of the first and second type,
respectively. In the recent literature it was suggested that
graphs with a small tightness of the first type are good models
for the multiprocessor interconnection networks. We study these
and some other types of tightness and some related graph
invariants and demonstrate their usefulness in the analysis of
multiprocessor interconnection networks. Tightness values for
graphs of some standard interconnection networks are determined.
We also present some fact showing that the tightness of the second
type is the relevant graph invariant. We prove that the number of
connected graphs with a bounded tightness is finite.
**

**
**

**
RUKOVODIOCI SEMINARA
**

**
Vera Kovačević-Vujčić
Milan Dražić
**