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.