More broadcast graphs. (English) Zbl 0936.05059
Let \(G\) be a graph. Broadcasting in \(G\) is the process of spreading information from one vertex, which knows the information, throughout \(G\) so that, in each time unit, any vertex which knows the information can pass it to at most one of its neighbours. Denote by \(B(n)\) the minimum number of edges over all graphs of order \(n\) which allow any vertex to broadcast in time \(\left\lceil \log n\right\rceil \). In the paper a new upper bound on \(B(n)\) is provided for some values of \(n\).
Reviewer: P.Horák (Safat)
MSC:
| 05C35 | Extremal problems in graph theory |
Keywords:
broadcast graphReferences:
| [1] | Ahlswede, R.; Gargano, L.; Haroutunian, H. S.; Khachatrian, L. H., Fault-tolerant minimum broadcast networks, Networks, 27, 293-307 (1996) · Zbl 0865.90046 |
| [2] | Bermond, J.-C; Fraigniaud, P.; Peters, J., Antepenultimate broadcasting, Networks, 26, 125-137 (1995) · Zbl 0856.90046 |
| [3] | Bermond, J.-C; Harutyunyan, H. A.; Liestman, A. L.; Perennes, S., A note on the dimensionality of modified Knödel graphs, Int. J. Found. Comp. Sci., 8, 109-117 (1997) · Zbl 0880.68097 |
| [4] | Bermond, J.-C; Hell, P.; Liestman, A. L.; Peters, J., Sparse broadcast graphs, Discrete Appl. Math., 36, 97-130 (1992) · Zbl 0764.05042 |
| [5] | Bermond, J.-C; Hell, P.; Liestman, A. L.; Peters, J., Broadcasting in bounded degree graphs, SIAM J. Discrete Math., 5, 10-24 (1992) · Zbl 0753.68007 |
| [6] | Chau, S. C.; Liestman, A. L., Constructing minimal broadcast networks, J. Combin. Inform. Systems Sci., 10, 110-122 (1985) · Zbl 0696.90077 |
| [7] | Chen, X., An upper bound for the broadcast function \(B(n)\), Chinese J. Comput., 13, 605-611 (1990) |
| [10] | Farley, A., Minimal broadcast networks, Networks, 9, 313-332 (1979) · Zbl 0425.94025 |
| [11] | Farley, A.; Hedetniemi, S. T.; Mitchell, S.; Proskurowski, A., Minimum broadcast graphs, Discrete Math., 25, 189-193 (1979) · Zbl 0404.05038 |
| [12] | Gargano, L.; Vaccaro, U., On the construction of minimal broadcast networks, Networks, 19, 673-689 (1989) · Zbl 0676.90021 |
| [13] | Grigni, M.; Peleg, D., Tight bounds on minimum broadcast networks, SIAM J. Discrete Math., 4, 207-222 (1991) · Zbl 0725.94016 |
| [15] | Hedetniemi, S. T.; Hedetniemi, S. M.; Liestman, A. L., A survey of broadcasting and gossiping in communication networks, Networks, 18, 319-349 (1988) · Zbl 0649.90047 |
| [17] | Knödel, W., New gossips and telephones, Discrete Math., 13, 95 (1975) · Zbl 0305.05001 |
| [18] | Labahn, R., A minimum broadcast graph on 63 vertices, Discrete Appl. Math., 53, 247-250 (1994) · Zbl 0807.94033 |
| [19] | Maheo, M.; Sacle, J.-F, Some minimum broadcast graphs, Discrete Appl. Math., 53, 275-285 (1994) · Zbl 0807.94028 |
| [20] | Mitchell, S.; Hedetniemi, S., A census of minimum broadcast graphs, J. Combin. Inform. Systems Sci., 5, 141-151 (1980) · Zbl 0449.05034 |
| [23] | Sacle, J.-F, Lower bound for the size in four families of minimum broadcast graphs, Discrete Math., 150, 359-369 (1996) · Zbl 0859.05052 |
| [24] | Ventura, J. A.; Weng, X., A new method for constructing minimal broadcast networks, Networks, 23, 481-497 (1993) · Zbl 0792.90028 |
| [25] | Weng, X.; Ventura, J. A., A doubling procedure for constructing minimal broadcast networks, Telecommun. Systems, 3, 259-293 (1995) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
