Search

All-to-all communication occurs in many important applications in parallel processing. In this paper, we study the all-to-all broadcast number (the shortest time needed to complete the all-to-all broadcast) of Cartesian product 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 Cartesian product of graphs and give formulas for the all-to-all broadcast numbers of some classes of graphs, such as the Cartesian product of two cycles, the Cartesian product of a cycle with a complete graph of odd order, the Cartesian product of two complete graphs of odd order, and the hypercube Q 2 n under this model. [ABSTRACT FROM AUTHOR]

Abstract: Given a graph , a defensive alliance of is a set of vertices satisfying the condition that for each , at least half of the vertices in the closed neighborhood of are in . A defensive alliance is called global if every vertex in is adjacent to at least one member of the defensive alliance . The global defensive alliance number of , denoted , is the minimum size around all the global defensive alliances of . In this paper, we present an efficient algorithm to determine the global defensive alliance numbers of trees, and further give formulas to decide the global defensive alliance numbers of complete -ary trees for . We also establish upper bounds and lower bounds for and , and show that the bounds are sharp for certain . [Copyright &y& Elsevier]

Abstract: Given a graph and a vertex subset of , the broadcasting time with respect to , denoted by , is the minimum broadcasting time when using as the broadcasting set. And the -broadcasting number, denoted by , is defined by . Given a graph and two vertex subsets , of , define , , , and for all . For all , , the -radius of , denoted by , is defined as , . In this paper, we study the relation between the -radius and the -broadcasting numbers of graphs. We also give the -radius and the -broadcasting numbers of the grid graphs, and the -broadcasting numbers of the complete -partite graphs and the hypercubes. [Copyright &y& Elsevier]