## Carlos J. Luz

## On the weighted Lovász number

In the beginning of this talk, the weighted Lovász number is defined and some reasons for its study are given. Then, a characterization of that number based on convex quadratic programming is presented. It is also shown how this characterization can be used to approximate or even to obtain a maximum independent set of a given graph.

Cristina Requejo

## The Minimum Weighted Tree Reconstruction problem

We address the Minimum Weighted Tree Reconstruction (MWTR) problem. This problem consists of constructing a tree connecting a set of terminal nodes and of associating weights to the edges such that the weight of the path between each pair of terminals is greater than or equal to a given distance between these terminals and the total weight of the tree is minimized. This problem has applications in several areas, namely, the inference of phylogenetic trees, the modeling of traffic networks and the analysis of internet infrastructures. We present mixed-integer linear programming models for the MWTR problem and discuss computational results obtained with two different sets of instances, one from the phylogenetic area and another from the telecommunications area. Robust optimization will also be discussed.

Joint work with: Olga Oliveira and Bernard Fortz.

Joint work with: Olga Oliveira and Bernard Fortz.

Paula Carvalho

## Adjacency and Laplacian spectra of powers of lexicographic products of graphs

Let H

^{k}[G] be the lexicographic product of two regular graphs H^{k}and G, where H^{k}is the lexicographic product of the graph H by himself k times. We determine the spectrum of H^{k}[G] and H^{k}when G and H are regular and the Laplacian spectrum of H^{k}[G] and H^{k}for G and H arbitrary graphs. Particular emphasis is given to the least eigenvalue of the adjacency matrix in the case of lexicographic powers of regular graphs, and to the algebraic connectivity and the largest Laplacian eigenvalues in the case of lexicographic powers of arbitrary graphs. This approach allows the determination of the spectrum (in case of regular graphs) and Laplacian spectrum (for arbitrary graphs) of huge graphs. As an example, the spectrum of the lexicographic power of the Petersen graph with the googol number (that is, 10^{100}) of vertices is determined. We finish with the extension of some well known spectral and combinatorial invariant properties of graphs to its lexicographic powers.**References:**

- Cardoso, D. M., M. A. de Freitas, E. A. Martins, M. Robbiano (2013). Spectra of graphs obtained
by a generalization of the join graph operation.
*Discrete Mathematics**313*, 733-741.