On Two Generalized Connectivities of Graphs

Sun, Yuefang  ; Li, Fengwei ; Jin, Zemin

Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 245-261.

Résumé

The concept of generalized k-connectivity κ_k (G), mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity. The pendant tree-connectivity τ_k (G) was also introduced by Hager in 1985, which is a specialization of generalized k-connectivity but a generalization of the classical connectivity. Another generalized connectivity of a graph G, named k-connectivity κ_k^' (G), introduced by Chartrand et al. in 1984, is a generalization of the cut-version of the classical connectivity. In this paper, we get the lower and upper bounds for the difference of κ_k^' (G) and τ_k(G) by showing that for a connected graph G of order n, if κ_k^' (G) n − k + 1 where k ≥ 3, then 1 ≤κ_k^' (G) − τ_k (G) ≤ n − k; otherwise, 1 ≤ κ_k^' (G) − τ_k(G) ≤ n − k + 1. Moreover, all of these bounds are sharp. We get a sharp upper bound for the 3-connectivity of the Cartesian product of any two connected graphs with orders at least 5. Especially, the exact values for some special cases are determined. Among our results, we also study the pendant tree-connectivity of Cayley graphs on Abelian groups of small degrees and obtain the exact values for τ_k(G), where G is a cubic or 4-regular Cayley graph on Abelian groups, 3 ≤ k ≤ n.

Détail

Mots-clés : k -connectivity, pendant tree-connectivity, Cartesian product, Cayley graph

Bibliographie

[1] S.B. Akers and B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput. 38 (1989) 555–566. doi:10.1109/12.21148

[2] L. Babai, Automorphism groups, isomorphism, reconstruction, in: Handbook of Combinatorics, R.L. Graham et al . (Ed(s)), (Elsevier, Amsterdam, 1995) 1447–1540.

[3] J.-C. Bermond, O. Favaron and M. Maheo, Hamiltonian decomposition of Cayley graphs of degree 4, J. Combin. Theory Ser. B 46 (1989) 142–153. doi:10.1016/0095-8956(89)90040-3

[4] N. Biggs, Algebraic Graph Theory (Cambridge University Press, New York, 1992).

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

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

[7] G. Chartrand, F. Okamoto and P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks 55 (2010) 360–367. doi:10.1002/net.20339

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

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

[10] C. Fan, D.R. Lick and J. Liu, Pseudo-cartesian product and hamiltonian decompositions of Cayley graphs on abelian groups, Discrete Math. 158 (1996) 49–62. doi:10.1016/0012-365X(95)00035-U

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

[12] M. Grötschel, A. Martin and R. Weismantel, The Steiner tree packing problem in VLSI design, Math. Program. 78 (1997) 265–281. doi:10.1007/BF02614374

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

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

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

[16] M.C. Heydemann, Cayley graphs and interconnection networks, in: Graph Symmetry, G. Hahn and G. Sabidussi (Ed(s)), (Kluwer Academic Publishers, Dordrecht, 1997) 167–224. doi:10.1007/978-94-015-8937-6_5

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

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

[19] S. Lakshmivarahan, J.-S. Jwo and S.K. Dhall, Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey, Parallel Comput. 19 (1993) 361–407. doi:10.1016/0167-8191(93)90054-O

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

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

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

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

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

[25] X. Li and Y. Mao, Generalized Connectivity of Graphs (SpringerBriefs in Mathematics, Springer, Switzerland, 2016).

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

[27] Y. Mao, On the pedant tree-connectivity of graphs . arXiv:1508.07149v1 [math.CO]

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

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

[30] N.A. Sherwani, Algorithms for VLSI Physical Design Automation, 3rd Edition (Kluwer Academic Publishers, London, 1999).

[31] W. Shiu, On 3-Regular and 4-Regular Cayley Graphs of Abelian Groups (Technical Report, Dept. of Mathematics, Hong Kong Baptist University, 1995).

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

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

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

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

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

[37] Y. Sun, A sharp lower bound for the generalized 3- edge-connectivity of strong product graphs, Discuss. Math. Graph Theory (2017), in press. doi:10.7151/dmgt.1982

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

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

[40] S. Zhou, A class of arc-transitive Cayley graphs as models for interconnection networks, SIAM J. Discrete Math. 23 (2009) 694–714. doi:10.1137/06067434X