torek, 10. maj 2011 Raziskovalni matematični seminar
V ponedeljek, 16. maja 2011, bosta v okviru raziskovalnega matematičnega seminarja v seminarski sobi v Galebu potekali dve predavanji.
Ob 9. uri bo predaval dr. Matjaž Kovše ( FNM, Univerza v Mariboru and IMFM, Ljubljana )
Ob 10. uri bo bo predaval dr. Boštjan Brešar ( FNM, Univerza v Mariboru and IMFM, Ljubljana ).
9:00 Matjaž Kovše:
Abstract: Given a subset $H$ of $k$ vertices in a connected graph $G$ the $k$-Steiner tree problem is that of finding a connected subgraph of $G$ that contains all the $k$ vertices and has the minimum number of edges among all such subgraphs. The number of edges in this subgraph is denoted by $s_G(H)$. It is well known that for $k \geq 3$, it is generally $NP$-hard to compute $s_G(H)$. The $k$-th Steiner index of a graph $G$ is defined as the sum of all values $s_G(H)$ where $H$ ranges over all subsets of $k$ vertices of $G$. For $k=2$ this definition coincides with the definition of well known and well studied Wiener index. Hamming graphs are the Cartesian products of complete graphs, and their isometric subgraphs are called partial Hamming graphs. A polynomial time algorithm for computing the $k$-th Steiner index of partial Hamming graphs will be presented. The main ingredient will be the canonical metric representation of a graph.
10:00 Boštjan Brešar:
Title: Median graphs and algebras
Abstract: In this talk we present a strong connection between certain ternary algebras, called median algebras, that enjoy three simple axioms, and the class of median graphs. The latter are defined as the graphs in which for any triple of vertices the three intervals between pairs of the triple share exactly one vertex. Median graphs are the most important class in metric graph theory, and appear in several applications in Computer science, mathematical biology and elsewhere.
We select a small portion of numerous characterizations and properties of median graphs, with an emphasis on some recent results.
