×

Broadcasting in planar graphs. (English) Zbl 0906.05071

It is known that for an arbitrary graph on \(n\) vertices, the minimum time required to broadcast is \(\lceil \log_2n\rceil\), and for any \(n\), there exist graphs on \(n\) vertices with broadcast time equal to \(\lceil\log_2 n\rceil\). When restricted to planar graphs, this is generally not the case. In this paper, the planar broadcast time for \(n\), \(b_p(n)\), has been defined as the minimum broadcast time for planar graphs on \(n\) vertices. It is shown that \(b_p(n)\) does not differ by much from \(\lceil\log_2 n\rceil\), and that just one extra time unit permits to broadcast even from low degree vertices in an efficient manner. A bound on the maximum number of vertices in a planar graph with a fixed broadcast time has also been derived.
Reviewer: B.K.Dass (Delhi)

MSC:

05C90 Applications of graph theory
05C35 Extremal problems in graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
94C15 Applications of graph theory to circuits and networks
PDFBibTeX XMLCite