Institutt for informatikk seminar: Thursday 28 June, kl. 14:15
Broadcasts in Graphs
Professor Stephen T. Hedetniemi
Clemson University, US
In his 1958 book, Berge introduced the coefficient of external stability, which was renamed the domination number by the Norwegian graph theorist Øystein Ore in his 1962 book. An application of domination was given by Liu in his 1968 book. Liu discussed the concept of dominance in communication networks, where a dominating set represents a set of cities which, having broadcast stations, can broadcast messages to every city in the network. It was assumed, however, that a given broadcast station could only transmit messages to adjacent nodes.
Since the publication of these three books, nearly 2000 research papers have been published on domination in graphs. Over the past 40 years more than 80 domination related parameters have been defined, most of which are listed in the appendix of the book by Haynes, Hedetniemi and Slater. But none of these models of domination have been based on the broadcast model of Liu, until recently when Erwin defined a model in which broadcast stations have an associated cost (or transmission power, say in watts) which enables them to broadcast messages to nodes at distances greater than one.
In this talk we note the similarity to Liu's 1968 model and extend
the study of broadcasts in graphs.
We say that a function
is a broadcast if for every vertex 
,
,
where 
denotes the diameter of 
and 
denotes
the eccentricity of 
. The cost of a broadcast is the
value
. We introduce and study the
minimum and maximum costs of several types of broadcasts in graphs,
including dominating, independent and efficient broadcasts.