Minimum broadcast graphs

  • Thread starter Dragonfall
  • Start date
  • #1
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?
 

Answers and Replies

  • #3
1,030
4
There must be some way out of here, said the Joker to the Thief.
 
  • #4
Interesting concept, but out of curiosity I wonder what gives you a reason to suspect that the answer to your question is known or even conceivably tractable? I don't believe we can come close to answering the question "For a given n, how many graphs on n vertices are there up to isomorphism?" but please correct me if I'm wrong.
 
  • #5
1,030
4
Frankly I have no idea. I was hoping someone here might.

EDIT: "For a given n, how many graphs on n vertices are there up to isomorphism?" I just re-read your question, and it would seem odd that this is not answered. I'm not good at combinatorics but I'm sure it's known.
 
Last edited:

Related Threads on Minimum broadcast graphs

Replies
4
Views
861
  • Last Post
Replies
4
Views
5K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
7
Views
4K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
12
Views
10K
Replies
2
Views
894
Replies
6
Views
2K
Top