在本篇論文中，我們提出了一個新的連結網路拓樸– the k-valent graphs。這個新的網路有許多良好的性質，首先它屬於凱氏圖（Cayley Graphs）– 對稱性（symmetric）和正規性（regular）。另外具有可變k 分支度degree）、小的直徑（logarithmic diameter）、以及最大容錯（maximal fault tolerance）。事實上， the k-valent graphs 是the trivalent Cayley graphs（Vadapalli and Srimani, 1995）的延伸。當k = 3，這兩個結構是同構的（isomorphic）。我們還設計了一個最短繞徑演算法並且討論一些托樸性質– Cycles or Cliques Embedding。

　　We propose a new family of Cayley graphs, named the k-valent graphs, for building interconnection networks. The k-valent graphs possess many valuable topological properties, such as regular with the node-degree k, logarithmic diameter subject to the number of nodes for some fxed k >= 6, and maximally fault tolerance. This new class also contains trivalent graphs (Vadapalli and Srimani, 1995) as its subclass of graphs. An algorithm is proposed to determine a shortest path between arbitrary two nodes. Besides, embedding of cycles or cliques on the k-valent graph is also discussed.

[1] S. B. Akers and B. Krishnamurthy, "The star graph: an attractive alternative
to n-cube," in Proceedings of International Conference on Parallel Processing, St. Charles, IL, pp. 555{556, 1987.
[2] S. B. Akers and B. Krishnamurthy, "A group-theoretic model for symmetric in-
terconnection networks," IEEE Transactions on Computers, 38(4):555{556, 1989.
[3] S. G. Akl, Parallel Computation: Models and Methods. Prentice Hall, 1997.
[4] L. Bhuyan and D. P. Agrawal, "Genereated hypercube and hyperbus structure for
a computer network," IEEE Transactions on Computers, bf33:323{333, 1984.
[5] L.N. Bhuyan and D.P. Agrawal, "Generalized Hypercube and Hyperbus Structures
for a Computer Network", IEEE Transactions on Computers, vol. 33, no. 4, pp.
323-333, 1984.
[6] C. Chen, D. P. Agrawal, and J. R. Burke, "dBCube: a new calss of hierarchical
multiprocessor interconnection networks with area e±cient laylot," IEEE Trans-
actions on Parallel and Distributed Systems, 4:1332-1344, 1993.
[7] G. H. Chen, J. S. Fu, and J. F. Fang, "Hypercomplete: a pancyclic recursive
topology for large-scale distributed multicomputer systems," Networks, 35(1):56{
69, 2000.
[8] K. Day and A. Tripathi, "Arrangement graphs: a class of generated star graphs,"Information Processing Letters, 42:235--241, 1992.
[9] A.W. Fu and S.-C. Chau, "Cyclic-Cubes: A New Family of Interconnection Net-
works of Even Fixed-Degrees," IEEE Trans. Parallel and Distributed System,
vol. 9, no. 12, pp. 1,253{1,268, Dec. 1998.
[10] K. Ghose and K. R. Desai, "Hierarchical cubic networks," IEEE Transactions on Parallel and Distributed Systems, 6:427{435, 1995.
[11] W. J. Hsu, "Fibonacci cubes: a new interconnection topology," IEEE Transactions on Parallel and Distributed Systems, 4:3{12, 1993.
[12] K. Hwang and J. Ghosh, "Hypernet: a communication-e±cient architecture for
constructing massively parallel computers," IEEE Transactions on Computers,
C-36:1450{1466, 1987.
[13] F.T. Leighton, Introduction to Parallel Algorithms and Architecture: Arrays,
Trees, Hypercubes. San Mateo: Morgan Kaufmann, 1992.
[14] Q. M. Malluhi and M. A. Bayoumi, "The hierarchical hypercube: a new intercon
nection topology for massively parallel systems," IEEE Transactions on Parallel
and Distributed Systems, 5:17{30, 1994.
[15] K. Menger, "Zur allgemeinen Kurventheorie," Fund. Math., 10:95-115, 1927.
[16] S. Ä Ohring and S. K. Das, Folded petersen cube networks: new competitors for the hypercubes," IEEE Transactions on Parallel and Distributed Systems, 7:151{168,
1996.
[17] S. Okawa, "Correction to the diameter of trivalent Cayley graphs," IEICE Transactions on Fundamentals, E84-A:1269{1272, 2001.
[18] F. P. Preparata and J. Vuillemin, "The cube-connected cycles: a versatile network for parallel computation," Communication of the ACM, 24:300{309, 1981.
[19] M. R. Samatham and D. K. Pradhan, "The de Bruijn multiprocessor network: a
versatile parallel processing and sorting networks for VLSI," IEEE Transactions
on Computers, C-38:567{581, 1989.
[20] G. Tel, Topics in Distributed Algorithms. Cambridge Int'l Series on Parallel Computation, Cambridge University Press, 1991.
[21] C.-H. Tsai, C.-N. Hung, L.-H. Hsu, and C.-H. Chang, "The correct diameter of
trivalent Cayley graphs," Information Processing Letters, 72:109{111, 1999.
[22] P. Vadapalli and P. K. Srimani, "Trivalent Cayley graphs for interconnection networks," Information Processing Letters, 54:329{335, 1995.
[23] P. Vadapalli and P. K. Srimani, "Shortest routing in trivalent Cayley graph network," Information Processing Letters, 57:183{188, 1996.
[24] P. Vadapalli and P. K. Srimani, "A new family of Cayley graph interconnection networks for constant degree four," IEEE Transactions on Parellel and Distributed Systems, 7:26-32, 1996.
[25] M. D.Wagh and J. Mo, "Hamilton cycles in Trivalent Cayley graphs," Information Processing Letters, 60:177{181, 1996.
[26] Douglas B. West, Introduction to graph theory, Prentice-Hall, Upper Saddle River, NJ 07458, 2001.
[27] Junming Xu, "Topological structure and analysis of interconnection networks," Kluwer Academic, 2001.