On the minimum size of graphs with given generalized connectivity.

Let G be a connected graph and S ⊆ V (G) with | S | ≥ 2. A tree T in G is called an S -tree if S ⊆ V (T). Two S -trees T 1 and T 2 are internally disjoint if E (T 1) ∩ E (T 2) = 0̸ and V (T 1) ∩ V (T 2) = S. For an integer k ≥ 2 , the generalized k -connectivity of a graph G , denoted by κ k (G) , is defined as κ k (G) = min { κ G (S) : S ⊆ V (G) and | S | = k } , where κ G (S) denotes the maximum number of pairwise internally disjoint S -trees in G. The generalized connectivity is a generalization of traditional connectivity. Let G n be the class of connected graphs of order n and let f (n , k , t) = min G ∈ G n { | E (G) | : κ k (G) = t }. In this paper, we prove f (n , k , t) ≥ ⌈ t (t + 2) 2 t + 2 n ⌉ for 4 ≤ k ≤ n and 1 ≤ t ≤ n − ⌈ k 2 ⌉. In particular, the lower bound is sharp when k = 4 and t = 2 (i.e., we explicitly provide a family of graphs fulfilling the bound in this case), improving the known results of Sun et al. (2021). [ABSTRACT FROM AUTHOR]