The Menger number of the Cartesian product of graphs

摘要

In a real-time system, the Menger number ζl(G) is an important measure of the communication efficiency and fault tolerance of the system G. In this paper, we obtain a lower bound for the Cartesian product graph. We show that ζl1+l2(G1×G2)<ζl1(G1)+ζl2(G2) for l1<2 and l2<2. As an application of the result, we determine the exact values ζl(G) of the grid network G=G(m1,m2,?,mn) for mi<2(1≤i≤n) and l<∑i=1nmi. This example shows that the lower bound of ζl1+l2(G1×G2) obtained is tight.