1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Minimum broadcast graphs

  1. Jun 3, 2009 #1
    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?
  2. jcsd
  3. Jun 4, 2009 #2
  4. Jun 11, 2009 #3
    There must be some way out of here, said the Joker to the Thief.
  5. Jun 11, 2009 #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.
  6. Jun 11, 2009 #5
    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: Jun 11, 2009
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook