排序方式: 共有9条查询结果,搜索用时 15 毫秒
1
1.
A k-disjoint path cover (k-DPC for short) of a graph is a set of k internally vertex-disjoint paths from given sources to sinks that collectively cover every vertex in the graph. In this paper, we establish a necessary and sufficient condition for the cube of a connected graph to have a 3-DPC joining a single source to three sinks. We also show that the cube of a connected graph always has a 3-DPC joining arbitrary two vertices. 相似文献
2.
Ping-Ying Tsai 《Information Processing Letters》2011,111(8):375-378
In a recently published paper [Z.-J. Xue, S.-Y. Liu, An optimal result on fault-tolerant cycle-embedding in alternating group graphs, Inform. Process. Lett. 109 (21-22) (2009) 1197-1201], the authors showed that for a set of faulty vertices F in an n-dimensional alternating group graph AGn, AGn−F remains pancyclic if |F|≤2n−6. However, the proof of the result is flawed. We will prove the theorem again correcting the defects in the previous proof. 相似文献
3.
Fault-Tolerant Hamiltonicity and Hamiltonian Connectivity of BCube with Various Faulty Elements
下载免费PDF全文
![点击此处可从《计算机科学技术学报》网站下载免费的PDF全文](/ch/ext_images/free.gif)
BCube is one kind of important data center networks. Hamiltonicity and Hamiltonian connectivity have significant applications in communication networks. So far, there have been many results concerning fault-tolerant Hamiltonicity and fault-tolerant Hamiltonian connectivity in some data center networks. However, these results only consider faulty edges and faulty servers. In this paper, we study the fault-tolerant Hamiltonicity and the fault-tolerant Hamiltonian connectivity of BCube(n, k) under considering faulty servers, faulty links/edges, and faulty switches. For any integers n ≥ 2 and k ≥ 0, let BCn,k be the logic structure of BCube(n, k) and F be the union of faulty elements of BCn,k. Let fv, fe, and fs be the number of faulty servers, faulty edges, and faulty switches of BCube(n, k), respectively. We show that BCn,k-F is fault-tolerant Hamiltonian if fv + fe + (n-1)fs ≤ (n-1)(k + 1)-2 and BCn,k-F is fault-tolerant Hamiltonian-connected if fv + fe + (n-1)fs ≤ (n-1)(k + 1)-3. To the best of our knowledge, this paper is the first work which takes faulty switches into account to study the fault-tolerant Hamiltonicity and the fault-tolerant Hamiltonian connectivity in data center networks. 相似文献
4.
In 1980, Jackson proved that every 2-connected k-regular graph with at most 3k vertices is Hamiltonian. This result has been extended in several papers. In this note, we determine the minimum number of vertices in a connected k-regular graph that is not Hamiltonian, and we also solve the analogous problem for Hamiltonian paths. Further, we characterize the smallest connected k-regular graphs without a Hamiltonian cycle. 相似文献
5.
Yi-Ching Chen 《Information Sciences》2010,180(13):2588-3675
An enhanced pyramid network is an alternate hierarchical structure for a pyramid network. This structure is created in a pyramid network by replacing each mesh with a torus at layers greater than one. This work studies the fault-tolerant Hamiltonian problem on the enhanced pyramid network and demonstrates that an enhanced pyramid network with two faulty nodes is Hamiltonian. The result is optimal, because edge connectivity and node connectivity of the enhanced pyramid network are both 4. 相似文献
6.
Behrooz Parhami 《Information Processing Letters》2008,107(6):246-251
Generalized Petersen (GP) networks and periodically regular chordal (PRC) rings have been proposed independently to ameliorate the high latency and extreme fragility of simple ring networks. In this paper, we note that certain GP networks are isomorphic to suitably constructed PRC rings, while other varieties correspond to PRC rings that closely approximate their topological and performance attributes. In the absence of equivalence and similarity proofs in the opposite direction, our results indicate that PRC rings may be preferable to GP networks in the sense of covering a broader family of networks and offering greater flexibility in cost-performance tradeoffs. 相似文献
7.
Hamiltonian properties on the class of hypercube-like networks 总被引:1,自引:0,他引:1
Chong-Dae Park 《Information Processing Letters》2004,91(1):11-17
Hamiltonian properties of hypercube variants are explored. Variations of the hypercube networks have been proposed by several researchers. In this paper, we show that all hypercube variants are hamiltonian-connected or hamiltonian-laceable. And we also show that these graphs are bipancyclic. 相似文献
8.
The augmented cube is a variation of hypercubes, it possesses many superior properties. In this paper, we show that, for any n-dimensional augmented cube (n?3) with faulty edges up to 4n-8 in which each vertex is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result is optimal with respect to the number of faulty edges tolerated. 相似文献
9.
Behrooz Parhami 《Information Processing Letters》2005,95(4):441-445
A two-level swapped (also known as optical transpose interconnect system, or OTIS) network with n2 nodes is built of n copies of an n-node basis network constituting its clusters. A simple rule for intercluster connectivity (node j in cluster i connected to node i in cluster j for all i≠j) leads to regularity, modularity, packageability, fault tolerance, and algorithmic efficiency of the resulting networks. We prove that a swapped network is Hamiltonian if its basis network is Hamiltonian. This general closure property for Hamiltonicity under swap or OTIS composition replaces a number of proofs in the literature for specific basis networks and obviates the need for proving Hamiltonicity for many other basis networks of potential practical interest. 相似文献
1