stresz119

$\begin{picture}(30,20) \put(0,0){\circle*{2}} \put(30,0){\circle*{2}} \put(0... ... \put(20,10){\line(-2,1){20}} \bezier{150}(14,12)(15,15)(16,13) \end{picture}$

$\textstyle \parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Matematyka Dyskretna
(prowadzone przez M.Woźniaka)

This will be a short survey on the scattering number (sc) of graphs and some relationships between sc and some other parameters of graphs. The scattering number of a non complete graph G is defined by $sc(G) = max \{c(G-X)-\vert X\vert : X \subset V(G)~$ and $~ c(G-X) > 1\}$ , where

denotes the number of components of

. The first appearance of this parameter is found in a paper of Jung (1978), and it is said by the author that this parameter is in a certain sense the additive dual for the concept of toughness

introduced by Chvatal (1973) in order to obtain sufficient conditions for hamiltonicity. The notion of toughness have been extensively studied, but it is not the case for the scattering number. This last parameter gives in some families of graphs more precise informations about the manner in which we can obtain a minimum path cover of a graph and how to construct a hamiltonian path or a hamitonian cycle if such a path or cycle exist. A survey of the main results obtained during the last two decades and some relationships between scattering number and some other parameters of graphs will be given.