Maximal Packing And Minimal Covering Of The Complete Bipartite Graph K_{m, N} With C₈

This thesis mainly considers about two issues.1. Let K_m,n denote the complete bipartite graph on m + n vertices with partite sets m and n. The decompositions of K_m,n(K_m,n^*) into Cycles of Length 2k have been solved by D.Sotteau, when m and n are even numbers, and m, n≥4. The decompositions of K_n,n\I into Cycles of Length 2k have been solved by Dan Archdeacon, etc., when n is odd number, and k≤n. In K_n,n \ I, I is the 1-factor of K_n,n. The maximal packing of K_m,n into Cycles of Length 4 has been solved by Elizabeth. J Billington, etc., and the maximal packing of K_m,n into Cycles of Length 6 has been solved by LaKeisha Brown, etc., when m or n is any number. Based on the above results, this thesis endeavors to solve the necessary and sufficient conditions for the existence of 8-cycle maximal packing and minimal covering of the complete bipartite graph K_n,m, when m or n is any number. By the parity of m and n, we take 3 cases into consideration. Firstly, m and n are even numbers; Secondly, m and n, one is even number and the other is odd number; Thirdly, m and n are odd numbers. We mainly use tools of direct construction in this part.2. Traffic grooming is one of the most important and popular problems in the area of optical networks. The technique of traffic grooming in WDM network helps to minimize the cost of a network and to alleviate the burden of end equipments. We hope to minimize the total number of WDM network add-drop mutiplexers (ADMs) required. This problem corresponds to a partition of the edges of the complete graph into subgraphs, where each subgraph has at most c edges (where c is the grooming ratio) and where the total number of vertices has to be minimized. For the given grooming ratio c, using tools of graph and design theory, we optimally solve the problem. Each class forms a single edge and no savings in drop cost is possible when c = 1. Classes contain at most two edges when c = 2, since the line graph of K_n is eulerian, so by tacking edges corresponding to consecutive vertices on an eulerian cycle it yields a drop cost. The minimum cost is '3n(n-1)/4'. The problem is sovled when c = 3, c = 4, c = 5 , c = 6, c≤n(n-1)/6. Based on the above results, this thesis studies traffic grooming in unidirectional WDM rings with grooming ratio c = 8. The existence of such decompositions with minimum cost is determined with finite number of possible exceptions, when each pair of sites employs no more than 1/8 of the wavelength capacity. Indeed when the number n of sites satisfies n = 0, 1, 2, 3, 4, 5, 6, 7 (mod 16), the values left undetermined are n = 34, 35, 36, 37, 38, 39. This thesis obtains these results. The techniques developed rely heavily on tools from graph theory and combinatorial design theory in this part.