Abstract: |
1. For a set of directed circuits of a graph G that form an oriented
circuit double cover, we denote by the graph with vertex set , in
which two circuits and are connected by edges if =.
Let , where the minimum is taken over all the
oriented circuit double covers of . It is easy to show that for any
graph , . On the other hand, it follows from well-known results
that for any integer , if and
only if ; for any integer ,
if and only if . This papers proves that for any rational number
there exists a graph for which . We
also show that there are graphs for which . 2. All-to-all communication occurs in many important applications in parallel pro-
cessing. In this talk, we study the all-to-all broadcast number (the shortest time
needed to complete the all-to-all broadcast) of graphs under the assumption that:
each vertex can use all of its links at the same time, and each communication link
is half duplex and can carry only one message at a unit of time. We give upper and
lower bounds for the all-to-all broadcast number of graphs and give formulas for the
all-to-all broadcast number of trees under this model. |
---|