標題: | The super connectivity of the pancake graphs and the super laceability of the star graphs |
作者: | Lin, CK Huang, HM Hsu, LH 資訊工程學系 Department of Computer Science |
關鍵字: | Hamiltonian;Hamiltonian connected;Hamiltonian laceable;connectivity |
公開日期: | 12-六月-2005 |
摘要: | A k-containerC(u, v) of a graph G is a set of k-disjoint paths joining u to v. A k-container C(u, v) of G is a k*-container if it contains all the vertices of G. A graph G is k*-connected if there exists a k*-container between any two distinct vertices. Let kappa(G) be the connectivity of G. A graph G is super connected if G is i*-connected for all 1 <= i <= kappa(G). A bipartite graph G is k*-laceable if there exists a k*-container between any two vertices from different parts of G. A bipartite graph G is super laceable if G is i*-laceable for all 1 <= i <= kappa(G). In this paper, we prove that the n-dimensional pancake graph P(n) is super connected if and only if n not equal 3 and the n-dimensional star graph S(n) is super laceable if and only if n not equal 3. (c) 2005 Elsevier B.V. All rights reserved. |
URI: | http://dx.doi.org/10.1016/j.tcs.2005.02.007 http://hdl.handle.net/11536/13582 |
ISSN: | 0304-3975 |
DOI: | 10.1016/j.tcs.2005.02.007 |
期刊: | THEORETICAL COMPUTER SCIENCE |
Volume: | 339 |
Issue: | 2-3 |
起始頁: | 257 |
結束頁: | 271 |
顯示於類別: | 期刊論文 |