2015/08/28 by Yaping Mao, Mao, Yaping · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems #math.CO
paper · pdf · doi:10.48550/arxiv.1508.07149
25 pages
arxiv created 2015/08/28 · openalex publication_date 2015/08/28 · arxiv updated 2015/08/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The concept of pedant tree-connectivity was introduced by Hager in 1985. For a graph G=(V,E) and a set S⊆ V(G) of at least two vertices, an S-Steiner tree or a Steiner tree connecting S (or simply, an S-tree) is a such subgraph T=(V',E') of G that is a tree with S⊆ V'. For an S-Steiner tree, if the degree of each vertex in S is equal to one, then this tree is called a pedant S-Steiner tree. Two pedant S-Steiner trees T and T' are said to be internally disjoint if E(T)∩ E(T')=\varnothing and V(T)∩ V(T')=S. For S⊆ V(G) and |S|≥ 2, the local pedant-tree connectivity τG(S) is the maximum number of internally disjoint pedant S-Steiner trees in G. For an integer k with 2≤ k≤ n, k-pedant tree-connectivity is defined as τk(G)=min\τG(S) | S⊆ V(G),|S|=k\. In this paper, we first study the sharp bounds of pedant tree-connectivity. Next, we obtain the exact value of a threshold graph, and give an upper bound of the pedant-tree k-connectivity of a complete multipartite graph. For a connected graph G, we show that 0≤ τk(G)≤ n-k, and graphs with τk(G)=n-k,n-k-1,n-k-2,0 are characterized in this paper. In the end, we obtain the Nordhaus-Guddum type results for pedant tree-connectivity.