G-design With Six Vertices And Twelve Edges And Its Applications

Let K_v be a complete graph with v vertices,and G a simple subgraph without isolate vertices of K_v.A G-design of K_v,denoted by(v,G,1)-GD,is a pair(X,B),where X is the vertex set of K_v,and B is the collection of sub-graphs(called blocks) of K_v,such that each block is isomorphic to G,and any edge in K_v occurs in exactly one block.There are five non-isomorphic graphs,each of which has six vertices and twelve edges.In this paper,we will discuss the existence problems of(v,G_i,1)-GD for i=1,…,5.Traffic grooming is one of the most important and popular issues in the area of optical networks.It refers to grouping low rate signals into higher speed streams,in order to reduce the equipment cost.In WDM networks,this cost is mostly given by the number of electronic terminations,namely Add-Drop Multiplexers(ADMs for short).We consider the undirected ring with a generic grooming factor c,and in this case,in graph-theoretical terms,the traffic grooming problem consists in partitioning the edges of a request graph into subgraphs with at most c edges,while minimizing the total number of vertices of the decomposition.For some grooming factors,using the graph and design theory,we optimally solve the problem.Based on the results of G-design with six vertices and twelve edges,we consider the problem of traffic grooming when c=12 and get the minimum number of ADMs.