- #1
Dragonfall
- 1,030
- 4
The "broadcast time" of a vertex v in a graph G is the number of time units it takes for a piece of information to go from v to every other vertex, provided that each vertex can communicate to only one other vertex during each time unit, and the information is transmitted in one time unit. The minimum broadcast time of a graph with n vertices is [tex]\lfloor\lg n\rfloor[/tex]. The broadcast time of a graph is the maximum broadcast time of all its vertices. A broadcast graph is "minimal" if the broadcast time of every vertex is floor{lg n} and has the least number of edges. For example, K_3 is a broadcast graph, but is not minimal because K_3 minus one edge achieves the same time bound for every vertex, yet has only 2 edges.
My question is: given n, how many different minimal broadcast graphs are there up to isomorphism?
My question is: given n, how many different minimal broadcast graphs are there up to isomorphism?