论文标题
关于完整两分图的路径连接性的注释
Note on Path-Connectivity of Complete Bipartite Graphs
论文作者
论文摘要
对于图$ g =（v，e）$和set $ s \ subseteq v（g）大小至少$ 2 $，如果$ g $中的路径是$ s $ path，如果它连接了$ s $的所有顶点。如果$ e（p_1）\ cap e（p_2）= \ emptyset $和$ v（p_1）\ cap v（p_2）= s $，则两个$ s $ paths $ p_1 $ $ p_1 $和$ p_2 $在内部不相交。令$π_g（s）$表示内部不相交的$ s $ Paths $ g $中的最大数量。然后将$ g $的$ k $ - path-connectivity $π_k（g）$ $ g $定义为最低$π_g（s）$，其中$ s $范围比所有$ v（g）$的所有$ k $ -subsets均超过所有$ k $ -subsets。在[ Hager，图形中的路径连接性，离散数学。 59（1986），53--59]，计算完整双分图$ k_ {a，b} $的$ k $ - path连接性，其中$ k \ geq 2 $。但是，从他的证据来看，只考虑了$ 2 \ leq k \ leq min \ {a，b \} $的情况。在本文中，我们计算出$ min \ {a，b \}+1 \ leq k \ leq a+b $并完成结果的情况。
For a graph $G=(V,E)$ and a set $S\subseteq 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)\cap E(P_2)=\emptyset$ and $V(P_1)\cap 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\geq 2$. But, from his proof, only the case that $2\leq k\leq min\{a,b\}$ was considered. In this paper, we calculate the the situation that $min\{a,b\}+1\leq k\leq a+b$ and complete the result.
