Geodesic
A Sharp Lower Bound For The Generalized 3-Edge-Connectivity Of Strong Product Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 4, pp. 975-988.

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

The generalized k-connectivity κ_k (G) of a graph G, mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized k-edge-connectivity which is defined as λ_k (G) = min{λ_G (S) | S ⊆ V (G) and |S| = k }, where λ_G (S) denote the maximum number 𝓁 of pairwise edge-disjoint trees T_1, T_2, . . ., T_𝓁 in G such that S ⊆ V (T_i) for 1 ≤ i ≤𝓁. In this paper we get a sharp lower bound for the generalized 3-edge-connectivity of the strong product of any two connected graphs.
Keywords: generalized connectivity, generalized edge-connectivity, strong product 
@article{DMGT_2017_37_4_a8,
     author = {Sun, Yuefang},
     title = {A {Sharp} {Lower} {Bound} {For} {The} {Generalized} {3-Edge-Connectivity} {Of} {Strong} {Product} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {975--988},
     publisher = {mathdoc},
     volume = {37},
     number = {4},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a8/}
}
TY  - JOUR
AU  - Sun, Yuefang
TI  - A Sharp Lower Bound For The Generalized 3-Edge-Connectivity Of Strong Product Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 975
EP  - 988
VL  - 37
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a8/
LA  - en
ID  - DMGT_2017_37_4_a8
ER  - 
%0 Journal Article
%A Sun, Yuefang
%T A Sharp Lower Bound For The Generalized 3-Edge-Connectivity Of Strong Product Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 975-988
%V 37
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a8/
%G en
%F DMGT_2017_37_4_a8
Sun, Yuefang. A Sharp Lower Bound For The Generalized 3-Edge-Connectivity Of Strong Product Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 4, pp. 975-988. http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a8/

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

[2] B. Breˇsar and S. Špacapan, Edge-connectivity of strong products of graphs, Discuss. Math. Graph Theory 27 (2007) 333-343. doi: 10.7151/dmgt.1365

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

[4] W.S. Chiue and B.S. Shieh, On connectivity of the Cartesian product of two graphs, Appl. Math. Comput. 102 (1999) 129-137. doi: 10.1016/S0096-3003(98)10041-3

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

[6] D. Du and X. Hu, Steiner Tree Problems in Computer Communication Networks (World Scientific, 2008). doi: 10.1142/6729

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

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

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

[10] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Second Edition (CRC Press, 2011).

[11] W. Imrich and S. Klavžar, Product Graphs-Structure and Recognition (Wiley, New York, 2000).

[12] W. Imrich, S. Klavžar and D.F. Rall, Topics in Graph Theory: Graphs and Their Cartesian Product (A K Peters, 2008).

[13] S. Klavžar and S. Špacapan, On the edge-connectivity of Cartesian product graphs, Asian-Eur. J. Math. 1 (2008) 93-98.

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

[15] H. Li, X. Li and Y. Sun, The generalized 3-connectivity of Cartesian product graphs, Discrete Math. Theor. Comput. Sci. 14 (2012) 43-54.

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

[17] X. Li and Y. Mao, On extremal graphs with at most ℓ internally disjoin Steiner trees connecting any n − 1 vertices, Graphs Combin. 31 (2015) 1-29. doi: 10.1007/s00373-014-1465-6

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

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

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

[21] X. Li, Y. Mao and L. Wang, Graphs with large generalized 3-edge-connectivity. arXiv:1201.3699v1 [math.CO]

[22] X. Li, J. Yue, and Y. Zhao, The generalized 3-edge-connectivity of lexicographic product graphs, Proc. COCOA 2014, Lecture Notes in Comput. Sci. 8881 (2014) 412-425. doi: 10.1007/978-3-319-12691-3 31

[23] B. Liouville, Sur la connectivité des produits de graphes, C.R. Acad. Sci. Paris Sér. A-B 286 (1978) A363-A365.

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

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

[26] G. Sabidussi, Graphs with given group and given graph theoretical properties, Canadian J. Math. 9 (1957) 515-525. doi: 0.4153/CJM-1957-060-7

[27] N.A. Sherwani, Algorithms for VLSI Physical Design Automation, 3rd Edition (Kluwar Acad. Pub., London, 1999).

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

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

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

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

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

[33] Y. Sun, On the maximum and minimum sizes of a graph with given k-connectivity, Discuss. Math. Graph Theory 37 (2017) 623-632. doi: 10.7151/dmgt.1941

[34] Y. Sun and X. Li, On the difference of two generalized connectivities of a graph, J. Comb. Optim. 33 (2017) 283-291. doi: 10.1007/s10878-015-9956-9.

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

[36] S. Špacapan, Connectivity of Cartesian products of graphs, Appl. Math. Lett. 21 (2008) 682-685. doi: 10.1016/j.aml.2007.06.010

[37] S. Špacapan, Connectivity of strong products of graphs, Graphs Combin. 26 (2010) 457-467. doi: 10.1007/s00373-010-0919-8

[38] J. Xu and C. Yang, Connectivity of Cartesian product graphs, Discrete Math. 306 (2006) 159-165. doi: 10.1016/j.disc.2005.11.010