The minimal size of graphs with given pendant-tree connectivity

2016/04/23 by Yaping Mao, Mao, Yaping
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1604.06862

19 pages. arXiv admin note: substantial text overlap with arXiv:1508.07202, arXiv:1508.07149, arXiv:1603.03995, arXiv:1604.01887; text overlap with arXiv:1103.6095 by other authors

arxiv created 2016/04/23 · arxiv updated 2016/04/26

Abstract

The concept of pendant-tree k-connectivity τ_k(G) of a graph G, introduced by Hager in 1985, is a generalization of classical vertex-connectivity. Let f(n,k,ℓ) be the minimal number of edges of a graph G of order n with τ_k(G)=ℓ (1≤ ℓ≤ n-k). In this paper, we give some exact value or sharp bounds of the parameter f(n,k,ℓ).

Citations

• Constructing Internally Disjoint Pendant Steiner Trees in Cartesian Product Networks
• On the pedant tree-connectivity of graphs
• Path connectivity of line graphs
• Pendant-tree connectivity of line graphs
• The generalized 3-connectivity of Cartesian product graphs

Related

• The minimal size of a graph with generalized connectivity κ₃ = 2
• The minimal size of a graph with given generalized 3-edge-connectivity
• Note on the minimal size of a graph with generalized connectivity kappa₃= 2
• Extremality and Sharp Bounds for the k-edge-connectivity of Graphs
• Pendant-tree connectivity of line graphs