Authors: Z. Jin, B. Sheng, Y. Sun Title: The minimum size of a graph with given tree connectivity Source: Discussiones Mathematicae Graph Theory Received 16.10.2017, Revised 28.11.2018, Accepted 28.11.2018, doi: 10.7151/dmgt.2193 | |
Abstract: 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})=\emptyset and V(T_{1})∩ V(T_{2})=S, and edge-disjoint if E(T_{1})∩ E(T_{2})=\emptyset. 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-\left ⌈\frac{k}{2}\right ⌉. 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. | |
Keywords: generalized connectivity, tree connectivity, generalized k-connectivity, generalized k-edge-connectivity, packing | |
Links: |