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

Shieh, Bih-Sheue

Networks 40, No. 2, 91-96 (2002).

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)

MSC:

05C40

Connectivity

References:

[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)