No Access

FAULT-TOLERANT MAXIMAL LOCAL-CONNECTIVITY ON CAYLEY GRAPHS GENERATED BY TRANSPOSITION TREES

LUN-MIN SHIH

Department of Computer Science, National Chiao Tung University, Hsinchu, Taiwan 30050, R.O.C.

Search for more papers by this author

CHIEH-FENG CHIANG

Department of Computer Science, National Chiao Tung University, Hsinchu, Taiwan 30050, R.O.C.

Search for more papers by this author

LIH-HSING HSU

Department of Computer Science and Information Engineering, Providence University, Taichung, Taiwan 43301, R.O.C.

Search for more papers by this author

, and

JIMMY J. M. TAN

Department of Computer Science, National Chiao Tung University, Hsinchu, Taiwan 30050, R.O.C.

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S021926590900256XCited by:9 (Source: Crossref)

Abstract

The local connectivity of two vertices is defined as the maximum number of internally vertex-disjoint paths between them. In this paper, we define two vertices as maximally local-connected, if the maximum number of internally vertex-disjoint paths between them equals the minimum degree of these two vertices. Moreover, we show that an (n-1)-regular Cayley graph generated by transposition tree is maximally local-connected, even if there are at most (n-3) faulty vertices in it, and prove that it is also (n-1)-fault-tolerant one-to-many maximally local-connected.

This work was supported in part by the National Science Council of the Republic of China under Contract NSC 96-2221-E-0009137-MY3.

Keywords:

References

S. B. Akers and B. Krishnamurthy, IEEE Trans. on Computers 38, 555 (1989), DOI: 10.1109/12.21148. Crossref, Web of Science, Google Scholar
J. A. Bondy and U. S. R. Murty , Graph theory with applications ( North Holland , New York , 1980 ) . Google Scholar
E. Cheng and L. Lipták, Information Sciences 177, 4877 (2007), DOI: 10.1016/j.ins.2007.05.034. Crossref, Web of Science, Google Scholar
G. A. Dirac, Math. Nachr. 22, 61 (1960), DOI: 10.1002/mana.19600220107. Crossref, Google Scholar
K. Menger, Fund. Math. 10, 95 (1927). Google Scholar
E. Oh and J. Chen, Discrete Applied Mathematics 129, 499 (2003), DOI: 10.1016/S0166-218X(02)00600-5. Crossref, Web of Science, Google Scholar
E. Oh and J. Chen, Journal of Interconnection Networks 4, 113 (2003), DOI: 10.1142/S0219265903000763. Link, Google Scholar
L. M. Shih and J. J. M. Tan, Strong Menger-Connectivity on the Class of Hypercubelike Networks, Proceedings of the International Computer Symposium 2 (2006) pp. 546–548. Google Scholar
L. M. Shihet al., Information Processing Letters 106, 64 (2008), DOI: 10.1016/j.ipl.2007.10.009. Crossref, Web of Science, Google Scholar
M. Tchuente, Ars Combinatoria 14, 115 (1982). Google Scholar
L. Volkmann, Applied Mathematics Letters 21, 63 (2008), DOI: 10.1016/j.aml.2006.12.014. Crossref, Web of Science, Google Scholar