Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs

被引：15

作者：

Chen, Xie-Bin ^{[1
]}

机构：

[1] Zhangzhou Teachers Coll, Dept Math & Informat Sci, Zhangzhou 363000, Fujian, Peoples R China

来源：

INFORMATION PROCESSING LETTERS | 2010年 / 110卷 / 06期

基金：

中国国家自然科学基金;

关键词：

Hypercube; Vertex-disjoint paths; Hamiltonian path; Matching; Folded hypercube; Interconnection network; FAULTY HYPERCUBES; PARTITIONS; NETWORKS; ELEMENTS; CYCLES;

D O I：

10.1016/j.ipl.2009.12.004

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Let W(n) denote any bipartite graph obtained by adding some edges to the n-dimensional hypercube Q(n) and let S and T be any two sets of k vertices in different partite sets of W(n) In this paper, we show that the graph W(n) has k vertex-disjoint (S, T)-paths containing all vertices of W(n) if and only if k = 2(n-1) or the graph W(n) - (S boolean OR T) has a perfect matching. Moreover, if the graph W(n) - (S boolean OR T) has a perfect matching M, then tile graph W(n) has k vertex-disjoint (S. T)-paths containing all vertices of W(n) and all edges in M. And some corollaries are given. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：203 / 205

页数：3

共 15 条

[1]

Bondy J.A., 1980, Graph Theory with Applications

[2] Spanning multi-paths in hypercubes [J].

Caha, Rostislav ;

Koubek, Vaclav .

DISCRETE MATHEMATICS, 2007, 307 (16) :2053-2066

[3] Many-to-many disjoint paths in faulty hypercubes [J].

Chen, Xie-Bin .

INFORMATION SCIENCES, 2009, 179 (18) :3110-3115

[4] Hamiltonian cycles with prescribed edges in hypercubes [J].

Dvorák, T .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2005, 19 (01) :135-144

[5] PARTITIONS OF FAULTY HYPERCUBES INTO PATHS WITH PRESCRIBED ENDVERTICES [J].

Dvorak, Tomas ;

Gregor, Petr .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2008, 22 (04) :1448-1461

[6] PROPERTIES AND PERFORMANCE OF FOLDED HYPERCUBES [J].

ELAMAWY, A ;

LATIFI, S .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1991, 2 (01) :31-42

[7] Perfect matchings extend to Hamilton cycles in hypercubes [J].

Fink, Jiri .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (06) :1074-1076

[8] Path partitions of hypercubes [J].

Gregor, Petr ;

Dvorak, Tomas .

INFORMATION PROCESSING LETTERS, 2008, 108 (06) :402-406

[9] A SURVEY OF THE THEORY OF HYPERCUBE GRAPHS [J].

HARARY, F ;

HAYES, JP ;

WU, HJ .

COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1988, 15 (04) :277-289

[10]

Jung-Heum Park, 2006, Journal of KISS: Computer Systems and Theory, V33, P789

← 1 2 →