In the design of large interconnection networks there is usually a need for each pair of nodes to communicate or to exchange data efficiently, but it is impractical to directly connect each pair of nodes. Therefore, the problem of designing networks is concerned with two constraints: the limitation of the number of connections attached to every node and also the limitation of the number of intermediate nodes on the communication route between any two given nodes. The first constraint is modeled by the degree of a node. One of the possible parameters that can be used to model the second constraint is the diameter. Thus in graph theoretical terms, the problem becomes the Degree/diameter problem For given d and k, find graphs (if the network is unidirectional) or digraphs (for a bi-directional network) of maximum degree or out-degree d and diameter at most k with maximum number of vertices nd,k. A well-known upper bound for nd,k is the so-called Moore bound that was first proposed by E.F. Moore.

In general, the degree/diameter problem is not an easy problem to solve. For instance, the existence of Moore graph of degree 57 and diameter 2 is a long-standing (42 years and counting!) and famous open problem in Graph Theory. Both approaches that are used to attack the problem, i.e.,

progressed slowly during the years; the gaps between the two bounds are still enormous, especially for large values of d and k.

Graph labelling of a graph G is a mapping f that sends some set of graph elements to a set of numbers (usually positive or non-negative integers) such that the vertex weight and/or the edge weight of the induces graph has some special properties. Labelled graphs serve as useful models for a broad range of applications such as: coding theory, x-ray crystallography, radar, astronomy, circuit design, communication network addressing and data base management.

Over the past three decades many variations of labelling have evolved and many papers have been written on the subject of graph labelling, but only a few general results on graph labelling. Indeed, the papers focus on particular classes of graphs and methods, and feature ad hoc arguments.

An important consideration in the design of communication networks as well as distributed computer system is the interconnected network. Several factors have to be taken into account in the design of interconnection networks, such as

Not every network follows a well-defined regular structure. For example, the World Wide Web, the Internet, the cellular network, even the science collaboration network, do not have a regular structure. The dynamic type of networks has a large number of nodes, and the connections are very “random" in the sense that the connections follow various organizing principles or plans but do not have any globally unique rules for the whole network. In another words, the topology of the Dynamic Networks is not the product of a deliberate engineering attempt aimed at obtaining the best global solution possible, but rather it reflects in great part the choices and decisions made by individual organizations whose subnets form the Dynamic Networks. With the dynamic nature of this type of network, no one knows what exactly is the structure of any particular Dynamic Networks.

Developing tools and measurements to characterize this type of network has been attracting more and more attention. Additionally, how to improve the performance of Dynamic Networks also become a interesting problem, the methods to be discovered are also can be applied to various areas such as to improve the search engine mechanics and to construct more efficient Web Site etc.

1. C. Balbuena, J. Tang, K. Marshall and Y. Lin, Super connectivity of regular graphs with small diameter, Discrete Applied Math., accepted 18 April 2008
2. J. Tang, M. Miller and Y. Lin, HSAGA and its application for the construction of Near-Moore digraphs, Journal of Discrete Algorithms, 6(1) (2008) 73-84
3. Y. Lin, M. Miller, C. Balbuena and X. Marcote, On the connectivity of $(k,g)$-Cages of even girth, Discrete Mathematics, 308 (2008) 3249-3256.
4. C. Balbuena, Y. Lin, M. Miller, Diameter-sufficient conditions for a graph to be super restricted connected, Discrete Applied Mathematics, 156(15) (2008) 2827-2834.
5. Lin, Y., Miller, M., Balbuena, C., Marcote, X., On the Connectivity of $(k,g)$-Cages of Even Girth, Discrete Mathematics, 308(15) (2008) 3249-3256.
6. C. Balbuena, J. Tang, Y. Lin, X. Marcote and M. Miller, A lower bound on the order of regular graphs with given girth pair, Journal of Graph Theory 55(2) (2007) ,155-163.
7. M. Bača, Y. Lin and M. Miller, Antimagic labelings of grids, Utilitas Math., 72 (2007), 65-75.
8. M. Bača, M.Z.Y. Elyamin, Y. Lin, M. Miller, Edge-antimagic graphs, Discrete Mathematics, Vol. 307, pp. 1232-1244, 2007.
9. M. Bača, Y. Lin, F.A. Muntaner-Batle, Normalized embedding of path-like trees, Utilitas Math., accepted for publication, Dec 2006.
10. M. Bača, Y. Lin F.A. Muntaner-Batle, Super edge-antimagic labelings of the path-like trees, Utilitas Math., 73 (2007), 117-128.
11. M. Bača, Y. Lin, F.A. Muntaner-Batle, Edge-antimagic labelings of forest, Utilitas Math., accepted for publication, Jan 2007.
12. J. Tang, Y. Lin, M. Miller, Calculating the extremal number ex(v;{c_3,c_4,..,c_n}), Electronic Notes in Discrete Mathematics, 27 (2006), 101-102, 2006.
13. C. Balbuena, E. Barker, K. Das, M. Miller, J. Ryan, Slamin, K. Sugeng, M. Tkac, On the degrees of a strongly vertex-magic graph, Discrete Mathematics, 306(6) (2006), 539-551.
14. C. Balbuena, E. Barker, K. Das, Y. Lin, M. Miller and K.A. Sugeng, Consecutive magic graphs. Discrete Mathematics, 306(16) (2006), 1817-1829.
15. Y. Lin and K.A. Sugeng, Face antimagic labelings of plane graphs P_a^b, Ars combinatoria, 80 (2006), 259-273.
16. M. Bača, Y. Lin, M. Miller and J. Ryan, Antimagic labelings of Mobius grids, Ars Combinatoria, Ars Combin. 78 (2006), 3-13.
17. Y. Lin, M. Miller, C. Balbuena and X. Marcote, All (k;g)-cages are edge-superconnected, Networks, 47(2) (2006), 102-110.
18. K.A. Sugeng, M. Miller, Y. Lin and M. Bača, Super (a,d)-vertex- antimagic labelings, JCMCC, 55 (2005), 91-102.
19. M. Bača, E.T. Baskoro, M.Y. Cholily, S. Jendrol, Y. Lin, M. Miller, J. Ryan, R. Simanjuntak, Slamin and K.A. Sugeng, Conjectures and Open Problems on Face Antimagic Evaluations of Graphs, Journal of Indonesian Math. Society (MIHMI), 11 (2) (2005), 175-192.
20. Y. Lin, M. Miller, and C. Rodger, All (k;g)-cages are k-edge-connected, J. Graph Theory, 48 (2005), 219-227.
21. Y. Lin, M. Miller and C. Balbuena, Improved lower bound for the vertex connectivity of (delta;g)-cages, Discrete Mathematics, 299(1-3) (2005), 162-171.
22. Y. Lin, Slamin, M. Miller and M. Ba?a, On d-antimagic labelling of prisms, Ars Combinatoria, 72 (2004), 65-76.
23. Y. Lin, Slamin and M. Miller, On d-antimagic labelling of antiprisms, Utilitas Math., 64 (2003), 213-220.
24. M. Bača, Y. Lin, M. Miller, Valuations of plane quartic graphs, Journal of Combinatorial Mathematics and Combinatorial Computing (JCMCC), 41 (2002), 209-221.
25. Slamin, M. Bača, Y. Lin, M. Miller, R. Simanjuntak, Edge-magic total labelings of wheels, fans and friendship graphs, Bulletin of ICA, 35 (2002), 89-98.