The Minimum Size of a Graph with Given Tree Connectivity

Sun, Yuefang ; Sheng, Bin  ; Jin, Zemin

Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 409-425.

Résumé

For a graph G = (V, E) and a set S ⊆ V of at least two vertices, an S-tree is a such subgraph T of G that is a tree with S ⊆ V(T). Two S-trees T_1 and T_2 are said to be internally disjoint if E(T_1) ∩ E(T_2) = ∅ and V(T_1) ∩ V(T_2) = S, and edge-disjoint if E(T_1) ∩ E(T_2) = ∅. The generalized local connectivity κ_G(S) (generalized local edge-connectivity λ_G(S), respectively) is the maximum number of internally disjoint (edge-disjoint, respectively) S-trees in G. For an integer k with 2 ≤ k ≤ n, the generalized k-connectivity (generalized k-edge-connectivity, respectively) is defined as κ_k(G) = minκ_G(S) | S ⊆ V(G), |S| = k (λ_k(G) = minλ_G(S) | S ⊆ V(G), |S| = k, respectively). Let f(n, k, t) (g(n, k, t), respectively) be the minimum size of a connected graph G with order n and κ_k(G) = t (λ_k(G) = t, respectively), where 3 ≤ k ≤ n and 1≤t≤n-⌈k/2⌉. For general k and t, Li and Mao obtained a lower bound for g(n, k, t) which is tight for the case k = 3. We show that the bound also holds for f(n, k, t) and is tight for the case k = 3. When t is general, we obtain upper bounds of both f(n, k, t) and g(n, k, t) for k ∈ 3, 4, 5, and all of these bounds can be attained. When k is general, we get an upper bound of g(n, k, t) for t ∈ 1, 2, 3, 4 and an upper bound of f(n, k, t) for t ∈ 1, 2, 3. Moreover, both bounds can be attained.

Détail

Keywords: generalized connectivity, tree connectivity, eneralized k-connectivity, generalized k-edge-connectivity, packing

Bibliographie

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

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

[3] L. Chen, X. Li, M. Liu and Y. Mao, A solution to a conjecture on the generalized connectivity of graphs, J. Comb. Optim. 33 (2017) 275–282. doi:10.1007/s10878-015-9955-x

[4] X. Cheng and D. Du, Steiner Trees in Industry (Dordrecht, Kluwer Academic Publisher, 2001).

[5] D. Cieslik, Steiner Minimal Trees (Nonconvex Optimization and Its Applications, Springer, 1998).

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

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

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

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

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

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

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

[13] S. Li, Some Topics on Generalized Connectivity of Graphs, PhD Thesis (Nankai University, 2012).

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

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

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

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

[18] X. Li and Y. Mao, Graphs with large generalized (edge)-connectivity, Discuss. Math. Graph Theory 36 (2016) 931–958. doi:10.7151/dmgt.1907

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

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

[21] Y. Mao, Steiner distance in graphs—a survey. arXiv:1708.05779.[math.CO]

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

[23] K. Ozeki and T. Yamashita, Spanning trees: a survey, Graphs Combin. 27 (2011) 1–26. doi:10.1007/s00373-010-0973-2

[24] E. Palmer, On the spanning tree packing number of a graph: a survey, Discrete Math. 230 (2001) 13–21. doi:10.1016/S0012-365X(00)00066-2

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

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

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

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

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

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