$\parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Zakładu Matematyki Dyskretnej
Wydziału Matematyki Stosowanej
AGH

We wtorek, 11 marca 2003 roku, o godzinie 12:45

w sali 304, łącznik A-3-A-4, A G H

Gabiel SEMANIŠIN

(Uniwersytet Szafarika, Koszyce)

wygłosi referat pod tytułem:

Non-traceable detour graphs

The detour order of a vertex $v$ in a graph $G$ is the length of the longest path beginning at $v$. The detour sequence of $G$ is the sequence of the detour orders of its vertices. The set of detour orders of the vertices of $G$ is called detour spectrum of $G$. A graph is called detour if its detour spectrum is one-element set. We deal with the problem of existence of a graph with a prescribed detour sequence $\Pi$. Particularly, we concentrate on the existence of detour graphs. The detour deficiency of a graph $G$ is the difference between the order of $G$ and its detour order. We show that for every positive integers $m\ge 1$ and $k\ge 2$ there is a non-traceable detour graphs with chromatic number $k$ and the detour deficiency at least $m$. This answers the question on the existence of non-traceable bipartite detour graphs formulated by F. Bullock.

Serdecznie zapraszamy wszystkich chętnych !