The 2-path-bipanconnectivity of hypercubes

被引:7
作者
Chen, Xie-Bin [1 ]
机构
[1] Zhangzhou Teachers Coll, Dept Math & Informat Sci, Zhangzhou 363000, Fujian, Peoples R China
关键词
Hypercube; Hamiltonian path; Panconnectivity; k-Path-panconnectivity; k-Disjoint path cover; Interconnection network; DISJOINT PATH COVERS; MAXIMAL CONNECTED COMPONENT; FAULTY VERTICES; EDGE-BIPANCYCLICITY; PRESCRIBED EDGES; DIAGNOSIS ALGORITHM; LONG PATHS; CYCLES; VERTEX; BIPANCONNECTIVITY;
D O I
10.1016/j.ins.2013.03.037
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
In this paper, we introduce the concept of the k-path-(bi)panconnectivity of (bipartite) graphs. It is a generalization of the (bi)panconnectivity and of the paired many-to-many k-disjoint path cover. The 2-path-bipanconnectivity with only one exception of the n-cube Q(n) (n >= 4) is proved. Precisely, the following result is obtained: In an n-cube with n >= 4 given any four vertices u(1), v(1), u(2), v(2) such that two of them are in one partite set and the another two are in the another partite set. Let s = t = 5 if C = u(1)u(2)v(1)v(2) is a cycle of length 4, and s = d(u(1), v(1)) + 1 and t = d(u(2), v(2)) + 1 otherwise, where d(u, v) denotes the distance between two vertices u and v. And let i and j be any two integers such that both i - s >= 0 and j - t >= 0 are even with i + j <= 2(n). Then there exist two vertex-disjoint (u(1), v(1))-path P and (u(2), v(2))-path R with vertical bar V(P)vertical bar = i and vertical bar V(R)vertical bar = j. As consequences, many properties of hypercubes, such as bipanconnectivity, bipanpositionable bipanconnectivity [18], bipancycle-connectivity [12], two internally disjoint paths with two given lengths, and the 2-disjoint path cover with a path of a given length [21], follow from our result. (C) 2013 Elsevier Inc. All rights reserved.
引用
收藏
页码:283 / 293
页数:11
相关论文
共 39 条
[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]   Cycles passing through prescribed edges in a hypercube with some faulty edges [J].
Chen, Xie-Bin .
INFORMATION PROCESSING LETTERS, 2007, 104 (06) :211-215
[4]   Edge-fault-tolerant diameter and bipanconnectivity of hypercubes [J].
Chen, Xie-Bin .
INFORMATION PROCESSING LETTERS, 2010, 110 (24) :1088-1092
[5]   Cycles passing through a prescribed path in a hypercube with faulty edges [J].
Chen, Xie-Bin .
INFORMATION PROCESSING LETTERS, 2010, 110 (16) :625-629
[6]   Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs [J].
Chen, Xie-Bin .
INFORMATION PROCESSING LETTERS, 2010, 110 (06) :203-205
[7]   Many-to-many disjoint paths in faulty hypercubes [J].
Chen, Xie-Bin .
INFORMATION SCIENCES, 2009, 179 (18) :3110-3115
[8]   On path bipancyclicity of hypercubes [J].
Chen, Xie-Bin .
INFORMATION PROCESSING LETTERS, 2009, 109 (12) :594-598
[9]   Hamiltonian cycles with prescribed edges in hypercubes [J].
Dvorák, T .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2005, 19 (01) :135-144
[10]   PARTITIONS OF FAULTY HYPERCUBES INTO PATHS WITH PRESCRIBED ENDVERTICES [J].
Dvorak, Tomas ;
Gregor, Petr .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2008, 22 (04) :1448-1461