The Conditional Connectivity of (n,k)-Star Graph

Ya Li Lv; Yong Hong Xiang

doi:10.4028/www.scientific.net/AMR.433-440.4853

Paper Titles

Application of a Grillage Model in Finite Element Analysis of Pre-Stressed Concrete Continuous Box-Girder
p.4837

Particle Swarm Clustering-Based Moving Object Segmentation in the H.264 Compressed Domain
p.4841

Multi-Target Tracking and Synergistic Management Based on Radar/ESM
p.4845

Digital Information Platform of Employment Based on Cloud Computing
p.4849

The Conditional Connectivity of (n,k)-Star Graph
p.4853

Research of University Comprehensive Information System Based on Cloud Computing
p.4857

Velocity and Attitude Matching of Transfer Alignment by Using H∞ Filter
p.4861

An Empirical Indoor Propagation Model for Underground Parking Area
p.4865

Dynamic Controller Based Linear Quadratic Optimal Control for Stabilization of Zero-Voltage-Switching Buck DC/DC Converters
p.4869

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 433-440The Conditional Connectivity of (n,k)-Star Graph

The Conditional Connectivity of (n,k)-Star Graph

Abstract:

Conditional connectivity has been proposed as an important parameter to estimate the fault tolerance of interconnection networks. In this paper, we consider the conditional connectivity of (n, k)-star graph. An (n, k)-star graph with dimension n (n ≥ 4) and order k can be partitioned into n subgraphs,. By utilizing this property, we give and proof the minimal cut-set and the minimal conditional cut-set of S _n,k. We hence obtain that the conditional connectivity of (n, k)-star graph S _n,k is n+k−3.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 433-440)

Pages:

4853-4856

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.433-440.4853

Citation:

Cite this paper

Online since:

January 2012

Authors:

Ya Li Lv, Yong Hong Xiang

Keywords:

(n,k)-Star Graph, Conditional Connectivity, Conditional Cut-Set, Conditional Set

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] H.C. Hsu Y.L. Hsieh, J.M. Tan, and L.H. Hsu, Fault Hamiltonicity and Fault Hamiltonian Connectivity of the (n, k)-Star Graphs，, Networks，2003, Vol. 42(4), pp.189-201.

DOI: 10.1002/net.10096

Google Scholar

[2] S.Y. Hsieh, Embedding Longest fault-free paths onto star graphs with more vertex faults, Theoretical Computer Science 337(2005), pp.370-378.

DOI: 10.1016/j.tcs.2005.01.018

Google Scholar

[3] W.K. Chiang, and R.J. Chen, The (n, k)-star graph: A generalized star graph, Inform. Process. Lett., 56(1995), pp.259-264.

Google Scholar

[4] W.K. Chiang and R.J. Chen, Topological Properties of the (n, k)-star graph, International Journal of Foundations of Computer Science, Vol. 9 , No. 2 (1998) , pp.235-248.

Google Scholar

[5] Q.P. Gu, and S. Peng, Node-to-set disjoint paths problem in star graphs, Inform. Process. Lett., 62(1997), pp.201-207.

DOI: 10.1016/s0020-0190(97)00059-8

Google Scholar

[6] F. Harary, Conditional connectivity, Networks 13(1983): 347-357.

Google Scholar

[7] Y. Rouskov, S. Latifi, P. k. Srimani, Conditional fault fiameter of star graph networks, Journal of Parallel and Distributed Computing, 33(1): 91-97, (1996).

DOI: 10.1006/jpdc.1996.0028

Google Scholar

[8] Lv Yali, and Ruan Xiaolong, The Conditional Fault Tolerance of (n, 2)-Star Graph, Information Science and Engineering(ICISE), 2010, pp.4767-4769.

DOI: 10.1109/icise.2010.5690258

Google Scholar