Connectivity And Fault-Diameter Of Product Graphs

Recently, the study of product graphs has been an active area of graph theory. Elegant and systematic theory has been built on the structure and recognition algorithms of four kinds of standard products of graphs (the Cartesian product, the strong product, the lexicographic product and the direct product). Moreover, the subject of product graphs and invariants is always a subject that is full of challenging problems. In the year 2000, Imrich and Klavzar wrote a monograph Product Graphs [21], which summarized all the above mentioned information about product graphs.Connectivity is one of the most basic and important invariants of graphs. In interconnection networks, connectivity, edge-connectivity, together with other concept related to the connectivity, such as maximal connected and super connected, are useful parameters to measure the reliability and fault-tolerance of interconnection networks. For most interconnection networks that are used in practice, their underlying topological structure can be defined using product graphs. Thus, the study of connectivity of product graphs is not only fundamental in the theory of product graphs, but also has application in interconnection networks. Until 2003, few result about the connectivity of product graphs can be seen in the literature, except some rough lower bounds for the connectivity of Cartesian products.In this article, we mainly study the connectivity of the four kinds of standard product graphs and a class of generalize product graphs. For the Cartesian product, we provedwhere G\ and G₂ are both finite or both infinite. This is a breakthrough, since there are only bounds for the connectivity of Cartesian product graphs previously. For the other three kinds of standard product graphs, we also obtained some exact formulas:For the generalized product graphs, we obtained the following (lower) bounds,Furthermore, for some kinds of the above product graphs, we also gave sufficient and necessary conditions for them to be maximal connected or super-connected.Fault-tolerant diameter is another important parameter in measuring the reliability of interconnection networks. In the end of this article, we also gave an upper bound for the fault-tolerant diameter of generalized product graphs,which generalized former results.