Back to Seminars
home page

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 $f: V \rightarrow \{0,1, \ldots, diam(G) \}$ is a broadcast if for every vertex $v \in V$, $f(v) \leq e(v)$, where $diam(G)$ denotes the diameter of $G$ and $e(v)$ denotes the eccentricity of $v$. The cost of a broadcast is the value $f(V) = \Sigma_{v \in V} f(v)$. We introduce and study the minimum and maximum costs of several types of broadcasts in graphs, including dominating, independent and efficient broadcasts.

Back to seminar homepage