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 T1 and T2 are said to be internally disjoint if E(T1)∩ E(T2)=\emptyset and V(T1)∩ V(T2)=S, and edge-disjoint if E(T1)∩ E(T2)=\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:
PDF