Maximally edge-connected and vertex-connected graphs and digraphs: A survey. (English) Zbl 1160.05038
Summary: Let \(D\) be a graph or a digraph. If \(\delta (D)\) is the minimum degree, \(\lambda (D)\) the edge-connectivity and \(\kappa (D)\) the vertex-connectivity, then \(\kappa (D)\leqslant \lambda (D)\leqslant \delta (D)\) is a well-known basic relationship between these parameters. The graph or digraph \(D\) is called maximally edge-connected if \(\lambda (D)=\delta (D)\) and maximally vertex-connected if \(\kappa (D)=\delta (D)\). In this survey we mainly present sufficient conditions for graphs and digraphs to be maximally edge-connected as well as maximally vertex-connected. We also discuss the concept of conditional or restricted edge-connectivity and vertex-connectivity, respectively.
MSC:
| 05C40 | Connectivity |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C35 | Extremal problems in graph theory |
| 05-02 | Research exposition (monographs, survey articles) pertaining to combinatorics |
Keywords:
connectivity; edge-connectivity; vertex-connectivity; restricted connectivity; conditional connectivity; super-edge-connectivity; local-edge-connectivity; minimum degree; degree sequence; diameter; girth; clique number; line graphReferences:
| [1] | Ayoub, J. N.; Frisch, I. T., On the smallest-branch cuts in directed graphs, IEEE Trans. Circuit Theory, CT-17, 249-250 (1970) · Zbl 0291.05112 |
| [2] | Balbuena, C.; Carmona, A., On the connectivity and superconnectivity of bipartite digraphs and graphs, Ars Combin., 61, 3-21 (2001) · Zbl 1071.05544 |
| [3] | Balbuena, C.; Carmona, A.; Fàbrega, J.; Fiol, M. A., On the connectivity and the conditional diameter of graphs and digraphs, Networks, 28, 97-105 (1996) · Zbl 0865.90047 |
| [4] | Balbuena, C.; Carmona, A.; Fàbrega, J.; Fiol, M. A., On the order and size of \(s\)-geodetic digraphs with given connectivity, Discrete Math., 174, 19-27 (1997) · Zbl 0886.05086 |
| [5] | Balbuena, C.; Cera, C.; Diánez, A.; Garcia-Vázquez, P.; Marcote, X., Sufficient conditions for \(\lambda^\prime \)-optimality of graphs with small conditional diameter, Inform. Process. Lett., 95, 429-434 (2005) · Zbl 1185.68081 |
| [6] | Balbuena, C.; Cera, C.; Diánez, A.; Garcia-Vázquez, P.; Marcote, X., Connectivity of graphs with given girth pair, Discrete Math., 307, 155-162 (2007) · Zbl 1109.05060 |
| [7] | Balbuena, C.; Fàbrega, J.; Marcote, X.; Pelayo, I., Superconnected digraphs and graphs with small conditional diameters, Networks, 39, 153-160 (2002) · Zbl 0999.05048 |
| [8] | Balbuena, C.; Garcia-Vázquez, P.; Marcote, X., Sufficient conditions for \(\lambda^\prime \)-optimality in graphs with girth \(g\), J. Graph Theory, 52, 73-86 (2006) · Zbl 1089.05024 |
| [9] | Balbuena, C.; Marcote, X., Lower connectivities of regular graphs with small diameter, Discrete Math., 307, 1255-1265 (2007) · Zbl 1118.05051 |
| [10] | Balbuena, C.; Marcote, X.; Garcia-Vázquez, P., On restricted connectivities of permutation graphs, Networks, 45, 113-118 (2005) · Zbl 1078.05050 |
| [11] | Bauer, D.; Suffel, C.; Boesch, F.; Tindell, R., Connectivity extremal problems and the design of reliable probabilistic networks, (The Theory and Application of Graphs, Kalamazoo MI, 1980 (1981), Wiley: Wiley New York), 45-54 · Zbl 0469.05044 |
| [12] | Bauer, D.; Tindell, R., Graphs with prescribed connectivity and line graph connectivity, J. Graph Theory, 3, 393-395 (1979) · Zbl 0422.05048 |
| [13] | Bauer, D.; Tindell, R., The connectivity of line and total graphs, J. Graph Theory, 6, 197-203 (1982) · Zbl 0457.05045 |
| [14] | Boesch, F., On unreliability polynomials and graph connectivity in reliable network synthesis, J. Graph Theory, 10, 339-352 (1986) · Zbl 0699.90041 |
| [15] | Boesch, F.; Chen, S., A generalization of line connectivity and optimally invulnerable graphs, SIAM J. Appl. Math., 34, 657-665 (1978) · Zbl 0386.05042 |
| [16] | Boesch, F.; Tindell, R., Circulants and their connectivities, J. Graph Theory, 8, 487-499 (1984) · Zbl 0549.05048 |
| [17] | Boesch, F.; Wang, J. F., Super-line-connectivity properties of circulant graphs, SIAM J. Algebraic Discrete Methods, 7, 89-98 (1986) · Zbl 0578.05046 |
| [18] | Boland, J. W.; Ringeisen, R. D., On super \(i\)-connected graphs, Networks, 24, 225-232 (1994) · Zbl 0805.05047 |
| [19] | Bollobás, B., On graphs with equal edge-connectivity and minimum degree, Discrete Math., 28, 321-323 (1979) · Zbl 0423.05026 |
| [20] | Bondy, J. A., Properties of graphs with constraints on the degrees, Studia Sci. Math. Hungar., 4, 473-475 (1969) · Zbl 0184.27702 |
| [21] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), The Macmillan Press: The Macmillan Press London, Basingstoke, UK · Zbl 1134.05001 |
| [22] | Bonsma, P.; Ueffing, N.; Volkmann, L., Edge-cuts leaving components of order at least three, Discrete Math., 256, 431-439 (2002) · Zbl 1017.05063 |
| [23] | Brouwer, A. E.; Mesner, D. M., The connectivity of strongly regular graphs, European J. Combin., 6, 215-216 (1985) · Zbl 0607.05045 |
| [24] | Capobianco, M.; Molluzzo, J. C., Examples and Counterexamples in Graph Theory (1978), North-Holland: North-Holland New York, Amsterdam, Oxford, \( \operatorname{xii} + 259\) pp · Zbl 0369.05021 |
| [25] | Carmona, A.; Fàbrega, J., On the superconnectivity and the conditional diameter of graphs and digraphs, Networks, 34, 197-205 (1999) · Zbl 0984.05052 |
| [26] | Chartrand, G., A graph-theoretic approach to a communications problem, SIAM J. Appl. Math., 14, 778-781 (1966) · Zbl 0145.20605 |
| [27] | Chartrand, G.; Harary, F., Graphs with prescribed connectivities, (Erdös, P.; Katona, G., Theory of Graphs (1968), Academic Press: Academic Press London, New York, San Francisco), 61-63 · Zbl 0186.27503 |
| [28] | Chartrand, G.; Kapoor, S. F.; Kronk, H. V., A sufficient condition for \(n\)-connectedness of graphs, Matematika, 15, 51-52 (1968) · Zbl 0175.20703 |
| [29] | Chartrand, G.; Lesniak, L., Graphs and Digraphs (1996), Chapman & Hall: Chapman & Hall London · Zbl 0890.05001 |
| [30] | Chartrand, G.; Stewart, M. J., The connectivity of line-graphs, Math. Ann., 182, 170-174 (1969) · Zbl 0167.52203 |
| [31] | Chen, Y. C.; Tan, J. J.M.; Hsu, L. H.; Kao, S. S., Super-connectivity and super-edge-connectivity for some interconnection networks, Appl. Math. Comput., 140, 245-254 (2003) · Zbl 1025.05037 |
| [32] | P. Dankelmann, A. Hellwig, L. Volkmann, On the connectivity of diamond-free graphs, Discrete Appl. Math. (2007).; P. Dankelmann, A. Hellwig, L. Volkmann, On the connectivity of diamond-free graphs, Discrete Appl. Math. (2007). · Zbl 1126.05064 |
| [33] | P. Dankelmann, A. Hellwig, L. Volkmann, Inverse degree and edge-connectivity, submitted for publication.; P. Dankelmann, A. Hellwig, L. Volkmann, Inverse degree and edge-connectivity, submitted for publication. |
| [34] | Dankelmann, P.; Volkmann, L., New sufficient conditions for equality of minimum degree and edge-connectivity, Ars Combin., 40, 270-278 (1995) · Zbl 0839.05065 |
| [35] | Dankelmann, P.; Volkmann, L., Degree sequence conditions for maximally edge-connected graphs and digraphs, J. Graph Theory, 26, 27-34 (1997) · Zbl 0879.05049 |
| [36] | Dankelmann, P.; Volkmann, L., Degree sequence conditions for maximally edge-connected graphs depending on the clique number, Discrete Math., 211, 217-223 (2000) · Zbl 0941.05019 |
| [37] | Daven, M.; Rodger, C. A., \((k, g)\)-Cages are 3-connected, Discrete Math., 199, 207-215 (1999) · Zbl 0927.05050 |
| [38] | Deng, H. Y.; Chen, J.; Li, Q. L.; Li, R. H., On the construction of most reliable networks, Discrete Appl. Math., 140, 19-33 (2004) · Zbl 1043.05069 |
| [39] | Erdös, P.; Sachs, H., Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 12, 251-257 (1963) · Zbl 0116.15002 |
| [40] | Esfahanian, A. H., Lower-bounds on the connectivities of a graph, J. Graph Theory, 9, 503-511 (1985) · Zbl 0664.05050 |
| [41] | Esfahanian, A. H., Generalized measures of fault tolerance with application to n-cube networks, IEEE Trans. Comput., 38, 1586-1591 (1989) |
| [42] | Esfahanian, A. H.; Hakimi, S. L., On computing a conditional edge-connectivity of a graph, Inform. Process. Lett., 27, 195-199 (1988) · Zbl 0633.05045 |
| [43] | Fàbrega, J.; Fiol, M. A., Maximally connected digraphs, J. Graph Theory, 13, 657-668 (1989) · Zbl 0688.05029 |
| [44] | Fàbrega, J.; Fiol, M. A., Extraconnectivity of graphs with large girth, Discrete Math., 127, 163-170 (1994) · Zbl 0797.05058 |
| [45] | Fàbrega, J.; Fiol, M. A., Bipartite graphs and digraphs with maximum connectivity, Discrete Appl. Math., 69, 271-279 (1996) · Zbl 0857.05063 |
| [46] | Fàbrega, J.; Fiol, M. A., On the extraconnectivity of graphs, Discrete Math., 155, 49-57 (1996) · Zbl 0857.05064 |
| [47] | Fàbrega, J.; Fiol, M. A., Further topics in connectivity, (Gross, J. L.; Yellen, J., Handbook of Graph Theory (2004), CRC Press: CRC Press London, New York), 300-329 |
| [48] | Fan, Y. M.; Xu, J. M.; Lu, M., The restricted edge-connectivity of Kautz undirected graphs, Ars Combin., 81, 369-379 (2006) · Zbl 1174.05426 |
| [49] | Faudree, R.; Flandrin, E.; Ryjáček, Z., Claw-free graphs—a survey, Discrete Math., 164, 87-147 (1997) · Zbl 0879.05043 |
| [50] | Fiol, M. A., Connectivity and superconnectivity of large graphs and digraphs, Ars Combin., 29B, 5-16 (1990) · Zbl 0708.05034 |
| [51] | Fiol, M. A., On super-edge-connected digraphs and bipartite digraphs, J. Graph Theory, 16, 545-555 (1992) · Zbl 0769.05062 |
| [52] | Fiol, M. A., The connectivity of large digraphs and graphs, J. Graph Theory, 17, 31-45 (1993) · Zbl 0783.05054 |
| [53] | Fiol, M. A., The superconnectivity of large digraphs and graphs, Discrete Math., 124, 67-78 (1994) · Zbl 0791.05068 |
| [54] | Fiol, M. A.; Fàbrega, J., On the distance connectivity of graphs and digraphs, Discrete Math., 125, 169-176 (1994) · Zbl 0796.05058 |
| [55] | M.A. Fiol, J. Fàbrega, M. Escudero, Short paths and connectivity in graphs and digraphs, in: The 12th British Combinatorial Conference, Norwich, 1989, Ars Combin. 29B (1990) 17-31.; M.A. Fiol, J. Fàbrega, M. Escudero, Short paths and connectivity in graphs and digraphs, in: The 12th British Combinatorial Conference, Norwich, 1989, Ars Combin. 29B (1990) 17-31. · Zbl 0708.05025 |
| [56] | G. Fricke, O.R. Oellermann, H.C. Swart, The edge-connectivity, average edge-connectivity and degree conditions, unpublished manuscript, 2000.; G. Fricke, O.R. Oellermann, H.C. Swart, The edge-connectivity, average edge-connectivity and degree conditions, unpublished manuscript, 2000. |
| [57] | Fu, H. L.; Huang, K. C.; Rodger, C. A., Connectivity of cages, J. Graph Theory, 24, 187-191 (1997) · Zbl 0866.05035 |
| [58] | D. Geller, F. Harary, Connectivity in digraphs, in: Recent Trends in Graph Theory, Proceedings of the First New York City Graph Theory Conference, 1970, Lecture Notes in Mathematics, vol. 186, 1971, pp. 105-115.; D. Geller, F. Harary, Connectivity in digraphs, in: Recent Trends in Graph Theory, Proceedings of the First New York City Graph Theory Conference, 1970, Lecture Notes in Mathematics, vol. 186, 1971, pp. 105-115. · Zbl 0214.23401 |
| [59] | Godsil, C.; Royle, G., Algebraic Graph Theory (2001), Springer: Springer Berlin · Zbl 0968.05002 |
| [60] | Goldsmith, D. L., On the \(n\) th order edge-connectivity of a graph, Congr. Numer., 32, 375-382 (1981) · Zbl 0492.05050 |
| [61] | Goldsmith, D. L., The functional edge-connectivity of a graph, J. Combin. Inform. System Sci., 17, 183-193 (1992) · Zbl 1230.05187 |
| [62] | Goldsmith, D. L.; Entringer, R. C., A sufficient condition for equality of edge-connectivity and minimum degree of a graph, J. Graph Theory, 3, 251-255 (1979) · Zbl 0417.05040 |
| [63] | Goldsmith, D. L.; White, A. T., On graphs with equal edge-connectivity and minimum degree, Discrete Math., 23, 31-36 (1978) · Zbl 0393.05035 |
| [64] | E. Győri, On division of graphs to connected subgraphs, in: Combinatorics, Proceedings of the Fifth Hungarian Colloquium, Keszthely, 1976, vol. I, pp. 485-494, Colloq. Math. Soc. János Bolyai 18 (1978).; E. Győri, On division of graphs to connected subgraphs, in: Combinatorics, Proceedings of the Fifth Hungarian Colloquium, Keszthely, 1976, vol. I, pp. 485-494, Colloq. Math. Soc. János Bolyai 18 (1978). · Zbl 0388.05008 |
| [65] | Hamidoune, Y. O., On the connectivity of Cayley digraphs, European J. Combin., 5, 309-312 (1984) · Zbl 0561.05028 |
| [66] | Hamidoune, Y. O.; Tindell, R., Vertex transitivity and super line connectedness, SIAM J. Discrete Math., 3, 524-530 (1990) · Zbl 0789.05053 |
| [67] | Harary, F., Conditional connectivity, Networks, 13, 347-357 (1983) · Zbl 0514.05038 |
| [68] | Harary, F.; Robinson, R. W., The diameter of a graph and its complement, Amer. Math. Monthly, 92, 211-212 (1985) · Zbl 0565.05046 |
| [69] | A. Hellwig, Maximally connected graphs and digraphs, Ph.D. Thesis, Aachen University, 2005.; A. Hellwig, Maximally connected graphs and digraphs, Ph.D. Thesis, Aachen University, 2005. · Zbl 1077.05054 |
| [70] | Hellwig, A.; Rautenbach, D.; Volkmann, L., Note on the connectivity of line graphs, Inform. Process. Lett., 91, 7-10 (2004) · Zbl 1178.68088 |
| [71] | Hellwig, A.; Rautenbach, D.; Volkmann, L., Cuts leaving components of given minimal order, Discrete Math., 292, 55-65 (2005) · Zbl 1063.05079 |
| [72] | Hellwig, A.; Volkmann, L., Maximally edge-connected digraphs, Australas. J. Combin., 27, 23-32 (2003) · Zbl 1020.05039 |
| [73] | Hellwig, A.; Volkmann, L., Maximally local-edge-connected graphs and digraphs, Ars Combin., 72, 295-306 (2004) · Zbl 1082.05055 |
| [74] | Hellwig, A.; Volkmann, L., Sufficient conditions for \(\lambda^\prime \)-optimality in graphs of diameter 2, Discrete Math., 283, 113-120 (2004) · Zbl 1042.05056 |
| [75] | Hellwig, A.; Volkmann, L., Neighborhood and degree conditions for super-edge-connected bipartite digraphs, Resultate Math., 45, 45-58 (2004) · Zbl 1050.05075 |
| [76] | Hellwig, A.; Volkmann, L., Sufficient conditions for graphs to be \(\lambda^\prime \)-optimal, super-edge-connected and maximally edge-connected, J. Graph Theory, 48, 228-246 (2005) · Zbl 1062.05084 |
| [77] | Hellwig, A.; Volkmann, L., Neighborhood conditions for graphs and digraphs to be maximally edge-connected, Australas. J. Combin., 33, 265-277 (2005) · Zbl 1077.05054 |
| [78] | Hellwig, A.; Volkmann, L., On connectivity in graphs with given clique number, J. Graph Theory, 52, 7-14 (2006) · Zbl 1100.05058 |
| [79] | Hellwig, A.; Volkmann, L., Lower bounds on the vertex-connectivity of digraphs and graphs, Inform. Process. Lett., 99, 41-46 (2006) · Zbl 1186.05077 |
| [80] | A. Hellwig, L. Volkmann, The connectivity of a graph and its complement, Discrete Appl. Math., to appear.; A. Hellwig, L. Volkmann, The connectivity of a graph and its complement, Discrete Appl. Math., to appear. · Zbl 1178.05055 |
| [81] | Imase, M.; Soneoka, T.; Okada, K., Connectivity of regular directed graphs with small diameters, IEEE Trans. Comput., 34, 267-273 (1985) · Zbl 0554.05044 |
| [82] | Imrich, W., On the connectivity of Cayley graphs, J. Combin. Theory Ser. B, 26, 323-326 (1979) · Zbl 0331.05114 |
| [83] | Jensen, J. L.W. V., Sur les fonctions convexes et les inégalités entre les valeurs moyennes, Acta Math., 30, 175-193 (1906) · JFM 37.0422.02 |
| [84] | Jiang, T.; Mubayi, D., Connectivity and separating sets of cages, J. Graph Theory, 29, 35-44 (1998) · Zbl 0919.05038 |
| [85] | Jolivet, J. L., Sur la connexité des graphes orientés, C. R. Acad. Sci. Paris, 274A, 148-150 (1972) · Zbl 0224.05110 |
| [86] | Kane, V. G.; Mohanty, S. P., A lower bound on the number of vertices of a graph, Proc. Amer. Math. Soc., 72, 211-212 (1978) · Zbl 0406.05044 |
| [87] | Kelmans, A. K., Asymptotic formulas for the probability of \(k\)-connectedness of random graphs, Theory Probab. Appl., 17, 243-254 (1972) · Zbl 0253.05136 |
| [88] | Knor, M.; Niepel, L.; So˘ltés, L., Centers in line graphs, Math. Slovaca, 43, 11-20 (1993) · Zbl 0772.05091 |
| [89] | König, D., Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math. Ann., 77, 453-465 (1916) · JFM 46.0146.03 |
| [90] | Latifi, S.; Hedge, M.; Naraghi-Pour, M., Conditional connectivity measures for large multiprocessor systems, IEEE Trans. Comput., 43, 218-222 (1994) |
| [91] | Lesniak, L., Results on the edge-connectivity of graphs, Discrete Math., 8, 351-354 (1974) · Zbl 0277.05123 |
| [92] | Li, L.; Xu, J. M., On restricted edge-connectivity of vertex-transitive graphs, J. Univ. Sci. Tech. China, 34, 266-272 (2004) · Zbl 1063.05080 |
| [93] | Li, Q. L.; Li, Q., Reliability analysis of circulant graphs, Networks, 31, 61-65 (1998) · Zbl 0929.05052 |
| [94] | Li, Q. L.; Li, Q., Super edge connectivity properties of connected edge symmetric graphs, Networks, 33, 157-159 (1999) · Zbl 0918.90076 |
| [95] | Li, T. F., Connectivity of circulant graphs, J. Math. Res. Exposition, 19, 608-610 (1999), (in Chinese, in English, Chinese summary) · Zbl 0938.05040 |
| [96] | Lin, Y.; Miller, M.; Balbuena, C.; Marcote, X., All \((k; g)\)-cages edge-superconnected, Networks, 47, 102-110 (2006) · Zbl 1087.05034 |
| [97] | Lin, Y.; Miller, M.; Rodger, C., All \((k; g)\)-cages are \(k\)-edge-connected, J. Graph Theory, 48, 219-227 (2005) · Zbl 1059.05066 |
| [98] | Liu, X., The connectivity of directed circulant graphs, J. Xinjiang Univ. Natur. Sci., 7, 31-34 (1990), (in Chinese, English summary) · Zbl 0964.05530 |
| [99] | Lovász, L., A homology theory for spanning trees of a graph, Acta Math. Acad. Sci. Hungar., 30, 241-251 (1977) · Zbl 0403.05040 |
| [100] | Lü, M.; Chen, G. L.; Xu, J. M., On super edge-connectivity of Cartesian product graphs, Networks, 49, 152-157 (2007) · Zbl 1118.05053 |
| [101] | Mader, W., Über den Zusammenhang symmetrischer Graphen, Arch. Math. (Basel), 21, 331-336 (1970) · Zbl 0201.56804 |
| [102] | Mader, W., Minimale \(n\)-fach kantenzusammenh”angende Graphen, Math. Ann., 191, 21-28 (1971) · Zbl 0198.29202 |
| [103] | W. Mader, Connectivity and edge-connectivity in finite graphs, in: B. Bollobás (Ed.), Surveys in Combinatorics, Proceedings of the Seventh British Combinatorial Conference, Cambridge, 1979, pp. 66-95, London Math. Soc. Lecture Note Series, vol. 38, Cambridge University Press, Cambridge, New York, 1979.; W. Mader, Connectivity and edge-connectivity in finite graphs, in: B. Bollobás (Ed.), Surveys in Combinatorics, Proceedings of the Seventh British Combinatorial Conference, Cambridge, 1979, pp. 66-95, London Math. Soc. Lecture Note Series, vol. 38, Cambridge University Press, Cambridge, New York, 1979. · Zbl 0404.05040 |
| [104] | Marcote, X.; Balbuena, C., Edge-superconnectivity of cages, Networks, 43, 54-59 (2004) · Zbl 1031.05078 |
| [105] | Marcote, X.; Balbuena, C.; Pelayo, I., On the connectivity of cages with girth five, six and eight, Discrete Math., 307, 1441-1446 (2007) · Zbl 1118.05054 |
| [106] | Marcote, X.; Balbuena, C.; Pelayo, I.; Fàbrega, J., \((\delta, g)\)-Cages with \(g \geqslant 10\) are 4-connected, Discrete Math., 301, 124-136 (2005) · Zbl 1079.05049 |
| [107] | Meng, J., Superconnectivity and super edge-connectivity of line graphs, Graph Theory Notes N. Y., 40, 12-14 (2001) |
| [108] | Meng, J., Optimally super-edge-connected transitive graphs, Discrete Math., 260, 239-248 (2003) · Zbl 1008.05084 |
| [109] | Meng, J., Connectivity of Cayley graphs on symmetric groups, J. Xinjiang Univ. Natur. Sci., 21, 113-119 (2004) |
| [110] | Meng, J.; Ji, Y., On a kind of restricted edge connectivity of graphs, Discrete Appl. Math., 117, 183-193 (2002) · Zbl 1007.05067 |
| [111] | Menger, K., Zur allgemeinen Kurventheorie, Fund. Math., 10, 96-115 (1927) · JFM 53.0561.01 |
| [112] | M.H. Moriarty, P.R. Christopher, Cages of degree \(k\) are \(k\)-edge-connected, in: The 36th Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Congr. Numer. 173 (2005) 161-167.; M.H. Moriarty, P.R. Christopher, Cages of degree \(k\) are \(k\)-edge-connected, in: The 36th Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Congr. Numer. 173 (2005) 161-167. · Zbl 1108.05055 |
| [113] | Oellermann, O. R., Connectivity and edge-connectivity in graphs: a survey, Congr. Numer., 116, 231-252 (1996) · Zbl 0905.05044 |
| [114] | Ou, J. P., Restricted edge connectivity of regular graphs, J. Math. Study, 34, 345-350 (2001) · Zbl 1002.05042 |
| [115] | J.P. Ou, Restricted edge connectivity and network reliability, Ph.D. Thesis, Department of Mathematics, Xiamen University, 2003.; J.P. Ou, Restricted edge connectivity and network reliability, Ph.D. Thesis, Department of Mathematics, Xiamen University, 2003. |
| [116] | Ou, J. P., 4-Restricted edge cuts of graphs, Australas. J. Combin., 30, 103-112 (2004) · Zbl 1053.05104 |
| [117] | Ou, J. P., Edge cuts leaving components of order at least \(m\), Discrete Math., 305, 365-371 (2005) · Zbl 1078.05052 |
| [118] | J.P. Ou, Ore-type conditions for maximizing 3-restricted edge connectivity of graphs, submitted for publication.; J.P. Ou, Ore-type conditions for maximizing 3-restricted edge connectivity of graphs, submitted for publication. |
| [119] | Ou, J. P.; Zhang, F. J., Bound on \(m\)-restricted edge-connectivity, Acta Math. Appl. Sinica (English Ser.), 19, 505-510 (2003) · Zbl 1049.05049 |
| [120] | Ou, J. P.; Zhang, F. J., Reliability of undirected de Bruijn networks, Gongcheng Shuxue Xuebao, 21, 947-952 (2004), (in Chinese, in English, Chinese summaries) · Zbl 1104.68344 |
| [121] | Ou, J. P.; Zhang, F. J., Super restricted edge connectivity of Kautz graphs, Acta Math. Sinica (Chinese Ser.), 47, 931-940 (2004), (in Chinese, in English, Chinese summaries) · Zbl 1119.05063 |
| [122] | Ou, J. P.; Zhang, F. J., 3-Restricted edge connectivity of vertex transitive graphs of girth three, J. Math. Res. Exposition, 25, 58-63 (2005) · Zbl 1071.05048 |
| [123] | Ou, J. P.; Zhang, F. J., 3-Restricted edge connectivity of vertex transitive graphs, Ars Combin., 74, 291-301 (2005) · Zbl 1074.05055 |
| [124] | Ou, J. P.; Zhang, F. J., 3-Restricted edge cut of graphs, Southeast Asian Bull. Math., 29, 1107-1111 (2005) · Zbl 1107.05053 |
| [125] | Ou, J. P.; Zhang, F. J., Super restricted edge connectivity of regular graphs, Graphs Combin., 21, 459-467 (2005) · Zbl 1089.05039 |
| [126] | Pelayo, I.; Balbuena, C.; Gómez, J., On the superconnectivity of generalized \(p\)-cycles, Discrete Math., 255, 13-23 (2002) · Zbl 1008.05085 |
| [127] | Plesník, J., Critical graphs of given diameter, Acta Fac. Rerum Natur. Univ. Commenian Math., 30, 71-93 (1975) · Zbl 0318.05115 |
| [128] | Plesník, J.; Znám, S., On equality of edge-connectivity and minimum degree of a graph, Arch. Math. (Brno), 25, 19-25 (1989) · Zbl 0731.05035 |
| [129] | Prisner, E., Line graphs and generalizations—a survey, Congr. Numer., 116, 193-229 (1996) · Zbl 0906.05061 |
| [130] | D. Rautenbach, L. Volkmann, Some remarks on \(\operatorname{\Lambda;}_{p , q} \)-connectedness, submitted for publication.; D. Rautenbach, L. Volkmann, Some remarks on \(\operatorname{\Lambda;}_{p , q} \)-connectedness, submitted for publication. |
| [131] | D. Rautenbach, L. Volkmann, Cyclic sums, network sharing and restricted edge cuts in graphs with long cycles, submitted for publication.; D. Rautenbach, L. Volkmann, Cyclic sums, network sharing and restricted edge cuts in graphs with long cycles, submitted for publication. · Zbl 1151.05029 |
| [132] | D. Rautenbach, L. Volkmann, On the existence of edge cuts leaving several large components, submitted for publication.; D. Rautenbach, L. Volkmann, On the existence of edge cuts leaving several large components, submitted for publication. · Zbl 1189.05091 |
| [133] | Ringel, G., Selbstkomplementäre Graphen, Arch. Math. (Basel), 14, 354-358 (1963) · Zbl 0114.40102 |
| [134] | Sampathkumar, E., Connectivity of a graph—a generalization, J. Combin. Inform. System Sci., 9, 71-78 (1984) · Zbl 0629.05043 |
| [135] | Seidman, S. B., Network structure and minimum degree, Social Networks, 5, 269-287 (1983) |
| [136] | Shang, L.; Zhang, H. P., Sufficient conditions for graphs to be \(\lambda^\prime \)-optimal and super-\( \lambda^\prime \), Networks, 49, 3, 234-242 (2007) · Zbl 1116.05045 |
| [137] | Shieh, B. S., Super edge- and point-connectivities of the Cartesian product of regular graphs, Networks, 40, 91-96 (2002) · Zbl 1018.05056 |
| [138] | Soneoka, T., Super edge-connectivity of dense digraphs and graphs, Discrete Appl. Math., 37/38, 511-523 (1992) · Zbl 0760.05050 |
| [139] | Soneoka, T.; Nakada, H.; Imase, M., Sufficient conditions for dense graphs to be maximally connected, Proc. ISCAS, 85, 811-814 (1985) |
| [140] | Soneoka, T.; Nakada, H.; Imase, M.; Peyrat, C., Sufficient conditions for maximally connected dense graphs, Discrete Math., 63, 53-66 (1987) · Zbl 0609.05050 |
| [141] | Sun, H. Q., The connectivity of line graphs, Chinese Ann. Math. Ser. A, 7, 602-605 (1986), (in Chinese) · Zbl 0629.05044 |
| [142] | Topp, J.; Volkmann, L., Sufficient conditions for equality of connectivity and minimum degree of a graph, J. Graph Theory, 17, 695-700 (1993) · Zbl 0794.05063 |
| [143] | Turán, P., An extremal problem in graph theory, Mat. Fiz. Lapok, 48, 436-452 (1941) · Zbl 0026.26903 |
| [144] | Tutte, W. T., A family of cubical graphs, Proc. Cambridge Philos. Soc., 43, 459-474 (1947) · Zbl 0029.42401 |
| [145] | Ueffing, N.; Volkmann, L., Restricted edge-connectivity and minimum edge-degree, Ars Combin., 66, 193-203 (2003) · Zbl 1078.05053 |
| [146] | Volkmann, L., Bemerkungen zum \(p\)-fachen Zusammenhang von Graphen, An. Univ. Bucuresti Mat., 37, 75-79 (1988) · Zbl 0649.05046 |
| [147] | Volkmann, L., Edge-connectivity in \(p\)-partite graphs, J. Graph Theory, 13, 1-6 (1989) · Zbl 0800.05008 |
| [148] | Volkmann, L., Fundamente der Graphentheorie (1996), Springer: Springer Wien, New York · Zbl 0844.05001 |
| [149] | Volkmann, L., Degree sequence conditions for equal edge-connectivity and minimum degree depending on the clique number, J. Graph Theory, 42, 234-245 (2003) · Zbl 1017.05066 |
| [150] | Volkmann, L., Degree sequence conditions for super-edge-connected graphs and digraphs, Ars Combin., 67, 237-249 (2003) · Zbl 1077.05056 |
| [151] | Volkmann, L., Sufficient conditions for super-edge-connected graphs depending on the clique number, J. Combin. Math. Combin. Comput., 49, 3-8 (2004) · Zbl 1052.05039 |
| [152] | Volkmann, L., Degree sequence conditions for maximally edge-connected oriented graphs, Appl. Math. Lett., 19, 1255-1260 (2006) · Zbl 1172.05323 |
| [153] | L. Volkmann, Graphen an allen Ecken und Kanten, vol. XVI, RWTH Aachen, 2006, 377pp. \( \langle;\) http://www.math2.rwth-aachen.de/\( \sim;\) uebung/GT/graphen1.html \(\rangle;\).; L. Volkmann, Graphen an allen Ecken und Kanten, vol. XVI, RWTH Aachen, 2006, 377pp. \( \langle;\) http://www.math2.rwth-aachen.de/\( \sim;\) uebung/GT/graphen1.html \(\rangle;\). · Zbl 1110.05002 |
| [154] | L. Volkmann, Local-edge-connectivity in digraphs and oriented graphs, Discrete Math. (2007), doi:10.1016/j.disc.2007.03.051.; L. Volkmann, Local-edge-connectivity in digraphs and oriented graphs, Discrete Math. (2007), doi:10.1016/j.disc.2007.03.051. · Zbl 1133.05055 |
| [155] | L. Volkmann, Sufficient conditions for maximally edge-connected and super-edge-connected oriented graphs depending on the clique number, Ars Combin., to appear.; L. Volkmann, Sufficient conditions for maximally edge-connected and super-edge-connected oriented graphs depending on the clique number, Ars Combin., to appear. · Zbl 1249.05172 |
| [156] | Volkmann, L., Lower bounds on the vertex-connectivity of oriented graphs and bipartite oriented graphs, Utilitas Math., 73, 45-54 (2007) · Zbl 1145.05035 |
| [157] | L. Volkmann, Degree sequence conditions for maximally edge-connected and super-edge-connected oriented graphs depending on the clique number, Ars Combin., to appear.; L. Volkmann, Degree sequence conditions for maximally edge-connected and super-edge-connected oriented graphs depending on the clique number, Ars Combin., to appear. · Zbl 1265.05335 |
| [158] | L. Volkmann, On local connectivity of graphs, Appl. Math. Lett., to appear.; L. Volkmann, On local connectivity of graphs, Appl. Math. Lett., to appear. · Zbl 1134.05046 |
| [159] | Volkmann, L., Restricted arc-connectivity of digraphs, Inform. Process. Lett., 103, 234-239 (2007) · Zbl 1183.05046 |
| [160] | L. Volkmann, Degree sequence conditions for super-edge-connected oriented graphs, J. Combin. Math. Combin. Comput., to appear.; L. Volkmann, Degree sequence conditions for super-edge-connected oriented graphs, J. Combin. Math. Combin. Comput., to appear. · Zbl 1176.05045 |
| [161] | L. Volkmann, Edge-cuts leaving components of given minimal order, submitted for publication.; L. Volkmann, Edge-cuts leaving components of given minimal order, submitted for publication. |
| [162] | Wang, P.; Xu, B.; Wang, J., A note on the edge-connectivity of cages, Electron. J. Combin., 10, 2 (2003), 4pp. · Zbl 1016.05047 |
| [163] | Wang, Y. Q., Super restricted edge-connectivity of vertex-transitive graphs, Discrete Math., 289, 199-205 (2004) · Zbl 1056.05092 |
| [164] | Wang, Y. Q., Optimization problems of the third edge-connectivity of graphs, Sci. China Ser. A, 49, 791-799 (2006) · Zbl 1108.05056 |
| [165] | Wang, Y. Q.; Li, Q., Super edge connectivity properties of graphs with diameter, J. Shanghai Jiaotong Univ., 33, 6, 646-649 (1999), (Chinese Ed.) · Zbl 0967.05042 |
| [166] | Wang, Y. Q.; Li, Q., A sufficient condition for an equality between restricted edge-connectivity and minimum edge-degree of graphs, Appl. Math. J. Chinese Univ. Ser. A, 16, 269-275 (2001), (in Chinese, in English, Chinese summary) · Zbl 0988.05059 |
| [167] | Wang, Y. Q.; Li, Q., Conditional edge connectivity properties, reliability comparisons and transitivity of graphs, Discrete Math., 258, 205-214 (2002) · Zbl 1012.05101 |
| [168] | Wang, Y. Q.; Li, Q., Upper bound of the third edge-connectivity of graphs, Sci. China Ser. A, 48, 360-371 (2005) · Zbl 1085.05041 |
| [169] | Watkins, M. E., A lower bound for the number of vertices of a graph, Amer. Math. Monthly, 74, 297 (1967) · Zbl 0147.42901 |
| [170] | Watkins, M. E., Connectivity of transitive graphs, J. Combin. Theory, 8, 23-29 (1970) · Zbl 0185.51702 |
| [171] | Whitney, H., Congruent graphs and the connectivity of graphs, Amer. J. Math., 54, 150-168 (1932) · JFM 58.0609.01 |
| [172] | Wong, P. K., Cages—a survey, J. Graph Theory, 6, 1-22 (1982) · Zbl 0488.05044 |
| [173] | Wu, J.; Guo, G., Fault tolerance measures for \(m\)-ary \(n\)-dimensional hypercubes based on forbidden faulty sets, IEEE Trans. Comput., 47, 888-893 (1998) · Zbl 1392.68110 |
| [174] | Xu, B.; Wang, P.; Wang, J., On the connectivity of \((4,g)\)-cages, Ars Combin., 64, 181-192 (2002) · Zbl 1071.05546 |
| [175] | Xu, J. M., A sufficient condition for equality of arc-connectivity and minimum degree of a digraph, Discrete Math., 133, 315-318 (1994) · Zbl 0808.05068 |
| [176] | Xu, J. M., Restricted edge-connectivity of vertex-transitive graphs, Chinese J. Contemp. Math., 21, 369-374 (2000) |
| [177] | J.M. Xu, Super or restricted connectivity of graphs—a survey, unpublished manuscript, 2005.; J.M. Xu, Super or restricted connectivity of graphs—a survey, unpublished manuscript, 2005. |
| [178] | J.M. Xu, M. Lü, Y.M. Fan, The restricted edge-connectivity of de Bruijn undirected graphs, Ars Combin. 83 (2007) 321-333.; J.M. Xu, M. Lü, Y.M. Fan, The restricted edge-connectivity of de Bruijn undirected graphs, Ars Combin. 83 (2007) 321-333. · Zbl 1174.05072 |
| [179] | Xu, J. M.; Lü, M.; Ma, M.; Hellwig, A., Super connectivity of line graphs, Inform. Process. Lett., 94, 191-195 (2005) · Zbl 1184.68366 |
| [180] | Xu, J. M.; Xu, K. L., On restricted edge-connectivity of graphs, Discrete Math., 243, 291-298 (2002) · Zbl 1049.05050 |
| [181] | Zamfirescu, T., On a theorem of Chartrand, Kapoor and Kronk, Rend. Circ. Mat. Palermo, 18, 319-322 (1969) · Zbl 0226.05120 |
| [182] | Zamfirescu, T., On the line-connectivity of line-graphs, Math. Ann., 187, 305-309 (1970) · Zbl 0188.28802 |
| [183] | Zhang, X. M.; Xu, J. M., On connectivity of Möbius cubes, Math. Appl. (Wuhan), 17, 56-60 (2004) |
| [184] | Zhang, Z., Graph operations and super edge connectivity, J. Zhengzhou Univ. Natur. Sci. Ed., 36, 1-6 (2004) · Zbl 1067.05044 |
| [185] | Z. Zhang, Sufficient conditions for restricted-edge-connectivity to be optimal, Discrete Math. (2007), doi:10.1016/j.disc.2007.01.016.; Z. Zhang, Sufficient conditions for restricted-edge-connectivity to be optimal, Discrete Math. (2007), doi:10.1016/j.disc.2007.01.016. · Zbl 1134.05047 |
| [186] | Zhang, Z.; Meng, J. X., On optimally-\( \lambda^{(3)}\) transitive graphs, Discrete Appl. Math., 154, 1011-1018 (2006) · Zbl 1092.05032 |
| [187] | Zhang, Z.; Yuan, J., A proof of an inequality concerning \(k\)-restricted edge connectivity, Discrete Math., 304, 128-134 (2005) · Zbl 1081.05060 |
| [188] | Zhang, Z.; Yuan, J., Degree conditions for restricted-edge-connectivity and isoperimetric-edge-connectivity to be optimal, Discrete Math., 307, 293-298 (2007) · Zbl 1177.05067 |
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.
