2020/08/10 by Shasha Li, Yan Zhao, Li, Shasha +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2008.04051
openalex publication_date 2020/08/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G=(V,E) and a set S⊆ V(G) of size at least 2, a path in G is said to be an S-path if it connects all vertices of S. Two S-paths P1 and P2 are said to be internally disjoint if E(P1)∩ E(P2)=∅ and V(P1)∩ V(P2)=S. Let πG (S) denote the maximum number of internally disjoint S-paths in G. The k-path-connectivity πk(G) of G is then defined as the minimum πG (S), where S ranges over all k-subsets of V(G). In [M. Hager, Path-connectivity in graphs, Discrete Math. 59(1986), 53--59], the k-path-connectivity of the complete bipartite graph Ka,b was calculated, where k≥ 2. But, from his proof, only the case that 2≤ k≤ min\a,b\ was considered. In this paper, we calculate the the situation that min\a,b\+1≤ k≤ a+b and complete the result.