A Complete Solution to Spectrum Problem for Five-Vertex Graphs with Application to Traffic Grooming in Optical Networks


Creative Commons License

Ge G., Hu S., Kolotoglu E., Wei H.

JOURNAL OF COMBINATORIAL DESIGNS, vol.23, pp.233-273, 2015 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 23
  • Publication Date: 2015
  • Doi Number: 10.1002/jcd.21405
  • Journal Name: JOURNAL OF COMBINATORIAL DESIGNS
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.233-273
  • Yıldız Technical University Affiliated: Yes

Abstract

A G-design of order n is a decomposition of the complete graph on n vertices into edge-disjoint subgraphs isomorphic to G. Grooming uniform all-to-all traffic in optical ring networks with grooming ratio C requires the determination of graph decompositions of the complete graph on n vertices into subgraphs each having at most C edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The existence spectrum problem of G-designs for five-vertex graphs is a long standing problem posed by Bermond, Huang, Rosa and Sotteau in 1980, which is closely related to traffic groomings in optical networks. Although considerable progress has been made over the past 30 years, the existence problems for such G-designs and their related traffic groomings in optical networks are far from complete. In this paper, we first give a complete solution to this spectrum problem for five-vertex graphs by eliminating all the undetermined possible exceptions. Then, we determine almost completely the minimum drop cost of 8-groomings for all orders n by reducing the 37 possible exceptions to 8. Finally, we show the minimum possible drop cost of 9-groomings for all orders n is realizable with 14 exceptions and 12 possible exceptions.