A note on internally disjoint alternating paths in bipartite graphs |
| |
| Authors: | Dingjun Lou Lihua Teng |
| |
| Institution: | a Department of Computer Science, Zhongshan University, Guangzhou 510275, PR of China
b Department of Computer Science, Nihon University, Sakurajosui 3-25-40, Setagaya-Ku, Tokyo 156-8550, Japan |
| |
| Abstract: | Let G be a balanced bipartite graph with partite sets X and Y, which has a perfect matching, and let x∈X and y∈Y. Let k be a positive integer. Then we prove that if G has k internally disjoint alternating paths between x and y with respect to some perfect matching, then G has k internally disjoint alternating paths between x and y with respect to every perfect matching. |
| |
| Keywords: | Matching Alternating path |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
