On Generalized Diameter Of Networks (Graphs)

Graph parameters such as connectivity and diameter have been studied extensively due to their intrinsic importance in graph theory, combinatorics and their relarioiis to (and applications in) fault tolerance and transmission delay in communications networks. The advent of VLSI technology and fiber optics material science has enabled us to design massively parallel processing computer systems and fast and complicated communications networks. All these systems increase their reliability by studying (among other) the existence of two (or more) disjoint paths connecting any two nodes. To satisfy all these demands, we generalize diameter of graphs to generalized diameter of graphs. In this paper, we mainly study generalized wide diameter of graphs, especially wide diameter and Rabin number of graphs.In the following, we list the main works of our paper.1. We define the generalized diameter of graphs which unifies the definitions of diameter, wide diameter and Rabin number of graphs.2. A>regular ^-connected graphs, generalized Petersen graphs and permutation graphs are studied extensively in the design of networks.(1). Let/(n, k) = m&\{dk(G): G is a A;梤egular &梒onnected graph with n vertices}.Hsu and Luczak^ ' studied the function f(n. k). In this paper, we give an algorithm and prove that we can construct ^-regular ^-connected graphs on 2m vertices with the maximum ^--diameter using it. We also prove some known results about /(2m, k) and verify that we can get new values of /(2m, k} by our algorithm.(2). Petersen graph is well known in graph theory, a generalized Petersen graph, denoted by F(m, a), is defined as follows: Its vertex set is U U W, where U - { 1. We also studied the relation between 2-wide diameter of Pa(G] and the diameter ofG.3. The w-Rabin number and generalized diameter of graphs.(1) The w-Rabin number of a graph, denoted by rw(G], is the minimum I such that for any w + 1 distinct vertices x,yi..---,yw, there are w vertex-disjoint paths of lengths at most / connecting x to y\. y^, ??? yw, respectively. In this paper, we study the Rabin number of k-regular ^-connected graphs and prove that every fe-regular /-connected graph on n vertices has Rabin number at most n/2 and this upper bound cannot be improved when n = 2k-3 + i(k-2).(2) In this paper, we study the generalized fc-diameter of /c-regular k-connected graphs. We derive some properties of gdk(G) and show that every fc-regular /c-connected graph on n vertices has generalized fc-diameter at most n/2 and this upper bound is tight when n = 2k ?3 + i(k ?2).4. Circulant networks are widely used in the design of local networks and various parallel processing systems. Let N be an positive integer, let G(N\ 1, $2> ??? si) be a circulant network on N nodes, node i is adjacent to nodes i + l.i + sy, ?- ,i + si (mod N). respectively. There are many results for the case that 1 = 2. In this p.-iper. we mainly study the case / = 3, that is triple loop networks. The upper bounds for the diameters of triple loop networks are given. When N is limited, the conditions for the optimal triple loop networks are obtained.5. Mapping a small topology into a large one is an important problem for designing efficient networks. In [681. ibe authors have shown how to mapABSTRACTrings of even...