1. Note on Path-Connectivity of Complete Bipartite Graphs.
- Author
-
Gao, Xiaoxue, Li, Shasha, and Zhao, Yan
- Subjects
- *
COMPLETE graphs , *BIPARTITE graphs , *GRAPH connectivity , *MATHEMATICS - Abstract
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 P 1 and P 2 are said to be internally disjoint if E (P 1) ∩ E (P 2) = ∅ and V (P 1) ∩ V (P 2) = 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 K a , 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 situation that min { a , b } + 1 ≤ k ≤ a + b and complete the result. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF