A note on internally disjoint alternating paths in bipartite graphs

被引：5

作者：

Lou, DJ ^{[1
]}

Saito, A

Teng, LH

机构：

[1] Zhongshan Univ, Dept Comp Sci, Guangzhou 510275, Peoples R China

[2] Nihon Univ, Dept Comp Sci, Tokyo 1568550, Japan

来源：

DISCRETE MATHEMATICS | 2005年 / 290卷 / 01期

关键词：

matching; alternating path;

D O I：

10.1016/j.disc.2004.10.019

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a balanced bipartite graph with partite sets X and Y, which has a perfect matching, and let x is an element of X and y is an element of 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. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：105 / 108

页数：4