2015/08/28 by Yaping Mao, Mao, Yaping · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems #Optimization and Search Problems #math.CO
paper · pdf · doi:10.48550/arxiv.1508.07202
22 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, pedant tree k-connectivity is defined as τk(G)=min\τG(S) | S⊆ V(G),|S|=k\. In this paper, we prove that for any two connected graphs G and H, τ3(G\Box H)≥ min\3\lfloor(τ3(G))/(2)\rfloor,3\lfloor(τ3(H))/(2)\rfloor\. Moreover, the bound is sharp.