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