Name
Abstract | ||
|---|---|---|
Given a graph G=(V,E)
and an originator vertex v, broadcasting is an information disseminating process of transmitting a message from the vertex v to all vertices of the graph G as quickly as possible. A graph G on n vertices is called broadcast graph if the broadcasting from any vertex in the graph can be accomplished in ⌈logn⌉ time. A broadcast graph with the minimum number of edges is called minimum broadcast graph. The number of edges in a minimum broadcast graph on n vertices is denoted by B(n). A long sequence of papers present different broadcast graph constructions and upper bounds on B(n). In this paper, we improve the compounding method and construct new broadcast graphs with a better upper bound on B(n). Consequently, we show that B(n)≤(m−k+1)n−(2m−k+1−2)(m−2q+1)2q−1 for n∈[2m−1+1,2m−2m2+1], where n=2m−2k−d, m≥5, 2≤k≤m−2, 0≤d≤2k−1, and q=min(⌊m−22⌋,k−2). |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.dam.2018.09.015 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
Broadcasting,Minimum broadcast graph,Knodel graph | Journal | 280 |
ISSN | Citations | PageRank |
0166-218X | 1 | 0.35 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hovhannes A. Harutyunyan | 1 | 206 | 28.18 |
| Zhiyuan Li | 2 | 1380 | 155.70 |