Rooted level-disjoint partitions of Cartesian products

Petr Gregor, Riste Škrekovski, Vida Vukašinović Applied Mathematics and Computation, 2015, Vol. 266, pages: 244-258

abstract: In interconnection networks one often needs to broadcast multiple messages in parallel from a single source so that the load at each node is minimal. With this motivation we study a new concept of rooted level-disjoint partitions of graphs. In particular, we develop a general construction of level-disjoint partitions for Cartesian products of graphs that is efficient both in the number of level partitions as in the maximal height. As an example, we show that the hypercube Q n for every dimension n=3·i^2 or n=4·i^2 where i ≥ 0 has n level-disjoint partitions with the same root and with maximal height 3n−2. Both the number of such partitions and the maximal height are optimal. Moreover, we conjecture that this holds for any n ≥ 3.