×

On super connectivity of Cartesian product graphs. (English) Zbl 1153.05034

The super connectivity \(\kappa_1\), a more refined parameter than the connectivity \(\kappa\), of a connected graph \(G\) is the minimum number of vertices whose deletion results in a disconnected graph without isolated vertices.
This article provides bounds for \(\kappa_1\) of the Cartesian product of two connected graphs, that is, \[ \min\{\kappa(G_1)+2\kappa(G_2), 2\kappa(G_1)+\kappa(G_2)\}\leq\kappa_1(G_1\times G_2)\leq\min\{m\kappa(G_2), n\kappa(G_1)\} \] if \(G_1\neq K_m\) and \(G_2\neq K_n\), which generalizes the result of B. S. Shieh [“Super edge- and point-connectivities of the Cartesian product of regular graphs”, Networks 40, No. 2, 91–96 (2002; Zbl 1018.05056)] on the super connectedness of the Cartesian product of two regular graphs with maximum connectivity.
Particularly, this paper determines that \(\kappa_1(K_m\times K_n)=\min\{m+2n-4, 2m+n-4\}\) for \(m+n\geq 6\) and states sufficient conditions to guarantee \(\kappa_1(K_2\times G)=2\kappa(G)\). As a consequence, it is immediately obtained that the super connectivity of the \(n\)-cube is \(2n-2\) for \(n\geq 3\).

MSC:

05C40 Connectivity
05C35 Extremal problems in graph theory

Citations:

Zbl 1018.05056
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Balbuena, Extraconnectivity of graphs with large minimum degree and girth, Discrete Math 167-168 pp 85– (1997) · Zbl 0874.05033
[2] Balbuena, On the restricted connectivity and superconnectivity in graphs with given girth, Discrete Math 307 pp 659– (2007) · Zbl 1111.05053
[3] Balbuena, Reliability of interconnection networks modeled by a product of graphs, Networks 48 pp 114– (2006) · Zbl 1108.05053
[4] Balbuena, On restricted connectivities of permutation graphs, Networks 45 pp 113– (2005) · Zbl 1078.05050
[5] Ball, Complexity of network reliability computation, Networks 10 pp 153– (1980) · Zbl 0443.90038
[6] Boesch, Synthesis of reliable networks-A survey, IEEE Trans Reliab 35 pp 240– (1986) · Zbl 0603.90060
[7] Boesch, Circulants and their connectivities, J Graph Theory 8 pp 487– (1984)
[8] Chiue, On connectivity of the Cartesian product of two graphs, Appl Math Comput 102 pp 129– (1999) · Zbl 0927.05048
[9] Esfahanian, Generalized measures of fault tolerance with application to n-cube networks, IEEE Trans Comput 38 pp 1586– (1989)
[10] Esfahanian, On computing a conditional edge-connectivity of a graph, Info Process Lett 27 pp 195– (1988)
[11] Fábrega, Extraconnectivity of graphs with large girth, Discrete Math 127 pp 163– (1994) · Zbl 0797.05058
[12] Fiol, Short paths and connectivity in graphs and digraphs, Ars Combin 29 pp 17– (1990) · Zbl 0708.05025
[13] Foldes, A character of hypercubes, J Discrete Math 17 pp 155– (1977) · Zbl 0354.05045
[14] Li, Restricted connectivity and restricted fault diameter of some interconnection networks, DIMACS Ser Discrete Math Theor Comput Sci 21 pp 267– (1995) · Zbl 0864.05056
[15] Lü, Super connectivity of line graphs and digraphs, Acta Mathematicae Appl Sinica, Engl Ser 22 pp 43– (2006) · Zbl 1104.05041
[16] Mulder, n-cube and median graphs, J Graph Theory 4 pp 107– (1980) · Zbl 0427.05046
[17] Shieh, Super edge- and point-connectivities of the Cartesian product of regular graphs, Networks 40 pp 91– (2002) · Zbl 1018.05056
[18] Xu, Theory and application of graphs (2003) · Zbl 1035.05003
[19] Xu, Super connectivity of line graphs, Info Process Lett 94 pp 191– (2005) · Zbl 1184.68366
[20] Yang, Graph theoretic reliable analysis for the Boolean n-cube networks, IEEE Trans Circuits Syst 35 pp 1175– (1988)
[21] Yang, The number of spanning trees of the regular networks, Int J Comput Math 23 pp 185– (1988) · Zbl 0683.05016
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.