Wielandt type theorem for Cartesian product of digraphs

초록

We show that mn - 1 is an upper bound of the exponent of the Cartesian product D x E of two digraphs D and E on m, n vertices, respectively and we prove our upper bound is extremal when (m, n) = 1. We also find all D and E when the exponent of D x E is mn - 1. In addition, when m = n, we prove that the extremal upper bound of exp(D x E) is n(2) - n + 1 and only the Cartesian product, Z(n) x W-n, of the directed cycle and Wielandt digraph has exponent equals to this bound. (C) 2008 Elsevier Inc. All rights reserved.

키워드