Geodesic
Sharp Upper Bounds for Generalized Edge-Connectivity of Product Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 833-843.

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

The generalized k-connectivity κ_k (G) of a graph G was introduced by Hager in 1985. 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{λ (S) : S ⊆ V (G) and |S| = k }, where λ(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 study the generalized edge- connectivity of product graphs and obtain sharp upper bounds for the generalized 3-edge-connectivity of Cartesian product graphs and strong product graphs. Among our results, some special cases are also discussed.
Keywords: generalized edge-connectivity, Cartesian product, strong product, lexicographic product 
@article{DMGT_2016_36_4_a4,
     author = {Sun, Yuefang},
     title = {Sharp {Upper} {Bounds} for {Generalized} {Edge-Connectivity} of {Product} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {833--843},
     publisher = {mathdoc},
     volume = {36},
     number = {4},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a4/}
}
TY  - JOUR
AU  - Sun, Yuefang
TI  - Sharp Upper Bounds for Generalized Edge-Connectivity of Product Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 833
EP  - 843
VL  - 36
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a4/
LA  - en
ID  - DMGT_2016_36_4_a4
ER  - 
%0 Journal Article
%A Sun, Yuefang
%T Sharp Upper Bounds for Generalized Edge-Connectivity of Product Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 833-843
%V 36
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a4/
%G en
%F DMGT_2016_36_4_a4
Sun, Yuefang. Sharp Upper Bounds for Generalized Edge-Connectivity of Product Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 833-843. http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a4/

[1] J.A. Bondy and U.S.R. Murty, Graph Theory, GTM 244 (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. doi: 10.1002/net.20339

[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] M. Hager, Pendant tree-connectivity, J. Combin. Theory Ser. B 38 (1985) 179-189. doi: 10.1016/0095-8956(85)90083-8

[6] R. Hammack, W. Imrich and S. Klavˇzar, Handbook of Product Graphs, Second Edition (CRC Press, 2011).

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

[8] W. Imrich, S. Klavžar and D.F. Rall, Topics in Graph Theory: Graphs and Their Cartesian Product (Taylor & Francis, 2008).

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

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

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

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

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

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

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

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

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

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

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

[20] G. Sabidussi, Graphs with given group and given graph theoretical properties, Canadian J. Math. 9 (1957) 515-525.

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

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

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

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

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

[26] Y. Sun, F. Li and Z. Jin, On two generalized connectivities of graphs, submitted.

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

[28] Y. Sun, On the maximum and minimum sizes of a graph with given k-connectivity, accepted for publication in Discuss. Math. Graph Theory.

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

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

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

[32] C. Yang and J. Xu, Connectivity and edge-connectivity of strong product graphs, J. Univ. Sci. Technol. China 38 (2008) 449-455.