Geodesic
On the Maximum and Minimum Sizes of a Graph with Given k-Connectivity
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 623-632.

Voir la notice de l'article provenant de la source Library of Science

The concept of k-connectivity κk(G), introduced by Chartrand in 1984, is a generalization of the cut-version of the classical connectivity. For an integer k ≥ 2, the k-connectivity of a connected graph G with order n ≥ k is the smallest number of vertices whose removal from G produces a graph with at least k components or a graph with fewer than k vertices. In this paper, we get a sharp upper bound for the size of G with κk(G) = t, where 1 ≤ t ≤ n − k and k ≥ 3; moreover, the unique extremal graph is given. Based on this result, we get the exact values for the maximum size, denoted by g(n, k, t), of a connected graph G with order n and κk(G) = t. We also compute the exact values and bounds for another parameter f(n, k, t) which is defined as the minimum size of a connected graph G with order n and κk(G) = t, where 1 ≤ t ≤ n − k and k ≥ 3.
Mots-clés : k -connectivity, generalized connectivity, connectivity 
@article{DMGT_2017_37_3_a9,
     author = {Sun, Yuefang},
     title = {On the {Maximum} and {Minimum} {Sizes} of a {Graph} with {Given} {k-Connectivity}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {623--632},
     publisher = {mathdoc},
     volume = {37},
     number = {3},
     year = {2017},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/item/DMGT_2017_37_3_a9/}
}
TY  - JOUR
AU  - Sun, Yuefang
TI  - On the Maximum and Minimum Sizes of a Graph with Given k-Connectivity
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 623
EP  - 632
VL  - 37
IS  - 3
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/DMGT_2017_37_3_a9/
LA  - en
ID  - DMGT_2017_37_3_a9
ER  - 
%0 Journal Article
%A Sun, Yuefang
%T On the Maximum and Minimum Sizes of a Graph with Given k-Connectivity
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 623-632
%V 37
%N 3
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/DMGT_2017_37_3_a9/
%G en
%F DMGT_2017_37_3_a9
Sun, Yuefang. On the Maximum and Minimum Sizes of a Graph with Given k-Connectivity. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 623-632. https://geodesic-test.mathdoc.fr/item/DMGT_2017_37_3_a9/

[1] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, Berlin, 2008).

[2] G. Chartrand, S.F. Kappor, L. Lesniak and D.R. Lick, Generalized connectivity in graphs, Bull. Bombay Math. Colloq. 2 (1984) 1–6.

[3] G. Chartrand, F. Okamoto and P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks 55 (2010) 360–367.

[4] D.P. Day, O.R. Oellermann and H.C. Swart, The ℓ -connectivity function of trees and complete multipartite graphs, J. Combin. Math. Combin. Comput. 10 (1991) 183–192.

[5] R. Gu, X. Li and Y. Shi, The generalized 3 -connectivity of random graphs, Acta Math. Sinica 57 (2014) 321–330, in Chinese.

[6] M. Hager, Pendant tree-connectivity, J. Combin. Theory Ser. B 38 (1985) 179–189. doi:10.1016/0095-8956(85)90083-8

[7] H. Li, X. Li, Y. Mao and Y. Sun, Note on the generalized connectivity, Ars Combin. 114 (2014) 193–202.

[8] H. Li, X. Li and Y. Sun, The generalized 3 -connectivity of Cartesian product graphs, Discrete Math. Theor. Comput. Sci. 14 (2012) 43–54. doi:10.1016/j.commatsci.2011.09.003

[9] X. Li and Y. Mao, A survey on the generalized connectivity of graphs . arXiv:1207.1838[math.CO]

[10] X. Li and Y. Mao, On extremal graphs with at most ℓ internally disjoint Steiner trees connecting any n − 1 vertices, Graphs Combin. 31 (2015) 2231–2259. doi:10.1007/s00373-014-1500-7

[11] X. Li and Y. Mao, The generalized 3 -connectivity of lexicographic product graphs, Discrete Math. Theor. Comput. Sci. 16 (2014) 339–354. doi:10.1007/978-3-319-12691-3_31

[12] X. Li, Y. Mao and Y. Sun, On the generalized ( edge ) -connectivity of graphs, Australas. J. Combin. 58 (2014) 304–319.

[13] O.R. Oellermann, On the ℓ -connectivity of a graph, Graphs Combin. 3 (1987) 285–299. doi:10.1007/BF01788551

[14] O.R. Oellermann, A note on the ℓ -connectivity function of a graph, Congr. Numer. 60 (1987) 181–188.

[15] Y. Sun, Generalized 3-( edge ) -connectivity for undirected double-loop networks, J. Discrete Math. Sci. Cryptogr. 17 (2014) 19–28. doi:10.1080/09720529.2013.867672

[16] Y. Sun, Generalized 3 -edge-connectivity of Cartesian product graphs, Czechoslovak Math. J. 65 (2015) 107–117. doi:10.1007/s10587-015-0162-9

[17] Y. Sun, Generalized 3 -connectivity and 3 -edge-connectivity for the Cartesian products of some graph classes, J. Combin. Math. Combin. Comput. 94 (2015) 215–225.

[18] Y. Sun, Maximum generalized local connectivities of cubic Cayley graphs on Abelian groups, J. Combin. Math. Combin. Comput. 94 (2015) 227–236.

[19] Y. Sun, Sharp upper bounds for generalized edge-connectivity of product graphs, Discuss. Math. Graph Theory 36 (2016) 833–843. doi:10.7151/dmgt.1924

[20] Y. Sun, A sharp lower bound for the generalized 3 -edge-connectivity of strong product graphs, Discuss. Math. Graph Theory, accepted.

[21] Y. Sun, F. Li and Z. Jin, On two generalized connectivities of graphs, Discuss. Math. Graph Theory, accepted.

[22] Y. Sun and X. Li, On the difference of two generalized connectivities of a graph, J. Comb. Optim. (2015), in press. doi:10.1007/s10878-015-9956-9

[23] Y. Sun and S. Zhou, Tree connectivities of Cayley graphs on Abelian groups with small degrees, Bull. Malays. Math. Sci. Soc. 39 (2016) 1673–1685. doi:10.1007/s40840-015-0147-8