##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Combinatorics

## Sebastian Cioaba

#### University of Delaware

## Spanning trees, toughness and spectrum of graphs

##### Abstract:

Kirchhoff's Matrix Tree Theorem is one of the classical results in spectral graph theory and it gives a formula for the number of spanning trees of a graph in terms of the eigenvalues of its Laplacian. In 1973, Chvatal introduced the notion of graph toughness and made two important conjectures: 1. Any graph with sufficiently large toughness is Hamiltonian. 2. Any graph with sufficiently large toughness is pancyclic. The first conjecture is still open, but the second conjecture was disproved by Alon who showed that there exist graphs with arbitrarily large toughness and girth. The key to Alon's argument was determining a close relation between the toughness of a regular graph and its eigenvalues. Independently and around the same time 1995, Brouwer found a slightly better result relating the toughness of a regular graph to its eigenvalues. In this talk, I will present some tight connections between the eigenvalues of a connected regular graph and the maximum number of edge-disjoint spanning trees in the graph that can be seen as a spectral version of Nash-Williams/Tutte Theorem. I will show some improvements of Brouwer's bound in certain ranges of toughness and discuss another problem of Brouwer related to the toughness of graphs attaining equality in the Hoffman ratio bound for the independence number. This is joint work with my Ph.D. student, Wiseley Wong.

Host: Fan Chung Graham

### November 2, 2012

### 4:00 PM

### AP&M 7321

****************************