Combinatorics, Graph Theory and Applications. COMBGRAF

Research Group on Graph Theory and Combinatorics

Brief history of the research group and summary of its activity

The research group on Graph Theory and Combinatorics, at the Applied Mathematics IV Department of the Universitat Politècnica de Catalunya (UPC), was founded in 1980 by Professors M.A. Fiol and J.L. Andrés Yebra. Nowadays there are around twenty five members whose research belongs to the area, developing research projects and/or conducting works directed toward PhD dissertations.

Currently, the group forms the research line UPC 33040601 of UPC, under the reponsibility of Prof. Josep Fabrega and Prof. Oriol Serra. It has been awarded by the Catalan Government the mention of Excellence Research group under grant 2000SGR 00079.

The group is in charge of the Discrete Mathematics section in the Ph.D. Program on Applied Mathematics of the UPC. Up to now, 26 doctorates have been awarded.

One of the main objectives of the group is the application of Graph Theory to the study and design of interconnection networks. The problems usually considered include the analysis of characteristic parameters of the network (diameter, connectivity measures, etc.), the study of special substructures (rings, trees, etc), routing algorithms, modularity properties and specific networks (symmetric networks, permutation networks, loop networks, etc).

 

  • Large Interconnection Networks. The design of large interconnection networks with bounded degree and diameter is still a subject of intense activity in the case of bidirectional networks and symmetric networks. In that sense, we keep an experimental version of the Table of largest (Degree, Diameter)-Graphs , that may be consulted interactively.
  • Fault-tolerance of different kinds of networks, measured both through their connectivity and through the vulnerability of their diameter.
  • Routing Algorithms and Routing Vulnerability in different sorts of networks and under different hypotheses.
  • Symmetric networks, in particular those modelled by Cayley digraphs are often considered. Symmetry in networks becomes useful both for the description and design of the network and for the simulation of a broader class of them.
  • Combinatorial Optimization Algorithms (simulated annealing and genetic algorithms) have also been considered for solving problems in the design of interconnection networks.
  • Permutation Networks and Applications, specially to the design, analysis and control of dynamic memory networks. Its use in multiprocessor involves also the study of new efficient storage schemes for storage of data in parallel memories.


Moreover, the group is also currently involved in research on several problems in the following topics:

 

  • Extremal Problems in Graphs.
  • Connectivity of Graphs.
  • Algebraic Graph Theory.
  • Distance-regularity.
  • Additive Group Theory.
  • Edge-coloring of Graphs.
  • Cayley Graphs.
  • Labelings and Graph Decompositions.
  • Combinatorial Group Theory.
  • Combinatorial Geometry.