Geodesic
Graphs with Large Generalized (Edge-)Connectivity
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 931-958.

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

The generalized k-connectivity κ_k (G) of a graph G, introduced by Hager in 1985, is a nice generalization of the classical connectivity. Recently, as a natural counterpart, we proposed the concept of generalized k-edge-connectivity λ_k (G). In this paper, graphs of order n such that κ_k (G) = n - k/2 - 1 and λ_k (G) = n - k/2 - 1 for even k are characterized.
Keywords: (edge-)connectivity, Steiner tree, internally disjoint trees, edge-disjoint trees, packing, generalized (edge-)connectivity 
@article{DMGT_2016_36_4_a12,
     author = {Li, Xueliang and Mao, Yaping},
     title = {Graphs with {Large} {Generalized} {(Edge-)Connectivity}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {931--958},
     publisher = {mathdoc},
     volume = {36},
     number = {4},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a12/}
}
TY  - JOUR
AU  - Li, Xueliang
AU  - Mao, Yaping
TI  - Graphs with Large Generalized (Edge-)Connectivity
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 931
EP  - 958
VL  - 36
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a12/
LA  - en
ID  - DMGT_2016_36_4_a12
ER  - 
%0 Journal Article
%A Li, Xueliang
%A Mao, Yaping
%T Graphs with Large Generalized (Edge-)Connectivity
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 931-958
%V 36
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a12/
%G en
%F DMGT_2016_36_4_a12
Li, Xueliang; Mao, Yaping. Graphs with Large Generalized (Edge-)Connectivity. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 931-958. http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a12/

[1] L.W. Beineke and R.J. Wilson, Topics in Structural Graph Theory (Cambrige University Press, 2013).

[2] F.T. Boesch and S. Chen, A generalization of line connectivity and optimally invulnerable graphs, SIAM J. Appl. Math. 34 (1978) 657-665. doi: 10.1137/0134052

[3] J.A. Bondy and U.S.R. Murty, Graph Theory (GTM 244, Springer, 2008).

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

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

[6] 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.

[7] D.L. Goldsmith, On the second-order edge-connectivity of a graph, Congr. Numer. 29 (1980) 479-484.

[8] D.L. Goldsmith, On the nth order connectivity of a graph, Congr. Numer. 32 (1981) 375-382.

[9] D.L. Goldsmith, B. Manval and V. Faber, Seperation of graphs into three components by removal of edges, J. Graph Theory 4 (1980) 213-218. doi: 10.1002/jgt.3190040209

[10] M. Grötschel, The Steiner tree packing problem in V LSI design, Math. Program. 78 (1997) 265-281. doi: 10.1007/BF02614374

[11] M. Grötschel, A. Martin and R. Weismantel, Packing Steiner trees: A cutting plane algorithm and commputational results, Math. Program. 72 (1996) 125-145.

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

[13] M. Hager, Path-connectivity in graphs, Discrete Math. 59 (1986) 53-59. doi: 10.1016/0012-365X(86)90068-3

[14] H.R. Hind, O.R. Oellermann, Menger-type results for three or more vertices, Congr. Numer. 113 (1996) 179-204.

[15] K. Jain, M. Mahdian and M. Salavatipour, Packing Steiner trees, in: Proc. 14th ACM-SIAM Symposium on Discrete Algorithms (Baltimore, 2003) 266-274.

[16] M. Kriesell, Edge disjoint trees containing some given vertices in a graph, J. Combin. Theory Ser. B 88 (2003) 53-65. doi: 10.1016/S0095-8956(02)00013-8

[17] M. Kriesell, Edge-disjoint Steiner trees in graphs without large bridges, J. Graph Theory 62 (2009) 188-198. doi: 10.1002/jgt.20389

[18] L. Lau, An approxinate max-Steiner-tree-packing min-Steiner-cut theorem, Combinatorica 27 (2007) 71-90. doi: 10.1002/jgt.20389

[19] W. Mader, Über die maximalzahl kantendisjunkter A-wege, Arch. Math. 30 (1978) 325-336. doi: 10.1007/BF01226062

[20] W. Mader, Über die maximalzahl kreuzungsfreier H-wege, Arch. Math. 31 (1978) 387-402. doi: 10.1007/BF01226465

[21] H. Li, X. Li and Y. Mao, On extremal graphs with at most two internally disjoint Steiner trees connecting any three vertices, Bull. Malays. Math. Sci. Soc. 37 (2014) 747-756.

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

[23] H. Li, X. Li, Y. Mao and J. Yue, Note on the spanning-tree packing number of lexicographic product graphs, Discrete Math. 338 (2015) 669-673. doi: 10.1016/j.disc.2014.12.007

[24] 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

[25] S. Li, W. Li and X. Li, The generalized connectivity of complete equipartition 3- partite graphs, Bull. Malays. Math. Sci. Soc. 37 (2014) 103-121.

[26] S. Li and X. Li, Note on the hardness of generalized connectivity, J. Comb. Optim. 24 (2012) 389-396. doi: 10.1007/s10878-011-9399-x

[27] S. Li, X. Li and W. Zhou, Sharp bounds for the generalized connectivity κ3(G), Discrete Math. 310 (2010) 2147-2163. doi: 10.1016/j.disc.2010.04.011

[28] X. Li and Y. Mao, Nordhaus-Gaddum-type results for the generalized edgeconnectivity of graphs, Discrete Appl. Math. 185 (2015) 102-112. doi: 10.1016/j.dam.2014.12.009

[29] 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

[30] X. Li and Y. Mao, The generalized 3-connectivity of lexicographical product graphs, Discrete Math. Theor. Comput. Sci. 16 (2014) 339-354.

[31] X. Li and Y. Mao, The minimal size of a graph with given generalized 3-edgeconnectivity, Ars Combin. 118 (2015) 63-72.

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

[33] C.St.J.A. Nash-Williams, Edge-disjoint spanning trees of finite graphs, J. Lond. Math. Soc. 36 (1961) 445-450. doi: 10.1112/jlms/s1-36.1.445

[34] O.R. Oellermann, Connectivity and edge-connectivity in graphs: A survey, Congr. Numer. 116 (1996) 231-252.

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

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

[37] F. Okamoto and P. Zhang, The tree connectivity of regular complete bipartite graphs, J. Combin. Math. Combin. Comput. 74 (2010) 279-293.

[38] N.A. Sherwani, Algorithms for VLSI Physical Design Automation, 3rd Edition (Kluwer Acad. Pub., Dordrecht, 1999).

[39] W. Tutte, On the problem of decomposing a graph into n connected factors, J. Lond. Math. Soc. 36 (1961) 221-230. doi: 10.1112/jlms/s1-36.1.221

[40] D. West and H. Wu, Packing Steiner trees and S-connectors in graphs, J. Combin. Theory Ser. B 102 (2012) 186-205.