Super edge- and point-connectivities of the Cartesian product of regular graphs. (English) Zbl 1018.05056

The author proves that the Cartesian product of two regular graphs with maximum edge-connectivity (i.e., \(\lambda(G)= d(G)\)) is super edge-connected except for the case \(K_2\times K_n\), \(n\geq 2\). Here super edge-connected means \(\lambda(G)= d(G)\) and each minimum edge-disconnectivity set isolates a vertex. Using this result (and a similar one about maximum vertex-connectivity) certain classes of networks which are recursively defined by Cartesian products are shown to possess super edge-connectivity (respectively, super vertex-connectivity).
Reviewer: M.Hager (Leonberg)


05C40 Connectivity
Full Text: DOI


[1] and ?Connectivity extremal problems and design of reliable probabilistic networks,? The theory and applications of graphs, and (Editors), Wiley, New York, 1981, pp. 45-54.
[2] Bauer, Networks 15 pp 257– (1985)
[3] Maximally reliable node weighted graphs, Proc 3rd Annu Princeton Conf Information Science and System, 1969, pp. 1-6. · Zbl 0293.05143
[4] Graph theory, Addison-Wesley, Reading, MA, 1969.
[5] Hawkes, IEEE Trans Comput C-34 pp 677– (1985)
[6] Latifi, IEEE Trans Comput 42 pp 27– (1993)
[7] Latifi, IEEE Trans Comput pp 218– (1994)
[8] Moore, J Franklin Inst 262 pp 191– (1956)
[9] and Connectivities of Cartesian products of graphs: Combinatorics, graph theory, algorithms and applications, Proc Third China-USA International Conf, Beijing, 1993, pp. 301-305.
[10] Provan, SIAM J Comput 12 pp 777– (1983)
[11] Graph theoretic reliability analysis of some interconnection networks, Ph.D. Dissertation, Institute of Electrical and Computer Engineering, National Cheng Kung University, 1987.
[12] Yang, IEEE Trans Circuits Syst 35 pp 1175– (1988)
[13] Yang, Int J Comput Math 23 pp 185– (1988)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.