As mentioned in Techniques for the
Construction
of Broadcast Graphs, constructing minimum
broadcast graphs is extremely difficult; furthermore, even
determining
the broadcast time of a vertex in an arbitrary graph is known to be
NP-complete.
Due to this difficulty, values for B(n)
are only known for n = 2k, n = 2k
- 2, and for a few values of n
| n | B(n) |
|
1
|
0
|
|
2
|
1
|
|
3
|
2
|
|
4
|
4
|
|
5
|
5
|
|
6
|
6
|
|
7
|
8
|
|
8
|
12
|
|
9
|
10
|
|
10
|
12
|
|
11
|
13
|
|
12
|
15
|
|
13
|
18
|
|
14
|
21
|
|
15
|
24
|
|
16
|
32
|
|
17
|
22
|
|
18
|
23
|
|
19
|
25
|
|
20
|
26
|
|
21
|
28
|
|
22
|
31
|
|
30
|
60
|
|
31
|
65
|
|
32
|
80
|
|
62
|
155
|
|
63
|
162
|
|
64
|
192
|
To obtain the value of B(n) for some n, one typically constructs a minimum broadcast graph on n vertices. This is a two-step process. First, one constructs a broadcast graph on n vertices having l edges; this establishes that B(n) £ l. One then shows that is is impossible to construct a broadcast graph having l - 1 edges, thus establishing that B(n) ³ l; a typical technique is to prove that in a connected graph G on n vertices having l - 1 edges that not every vertex can be the root of a spanning minimum broadcast tree. This completes the proof.
An example proof that B(7) = 8 comes from Farley et al. in [4]. The graph shown below establishes that B(7) £ 8:
Furthermore, the root of a minimum broadcast tree with 7 vertices must have degree 2. C7 is the only connected graph on 7 vertices having 7 edges and a minimum degree of 2, but it is not a broadcast graph; hence, B(7) > 7. This completes our proof.
For more such proofs, refer to [4].
