## Graph Theory 2005 @ Oberwolfach, Part 2

For the start of 2005, we have selected some open problems and conjectures that
were posed at the Oberwolfach meeting on Graph Theory in January 2005 (click
here for the conference photo). The first two problems have been published
in January. We conclude with two more.

### Problem 3 (by Nati Linial)

Let ** A** be an n x n matrix. If I is a subset of {1,...,n}x {1,...,n}, a *signing*
of ** A** with respect to I is the matrix ** B** such that B_{ij} = A_{ij}
if the pair (*i,j*) belongs to I, and B_{ij} = - A_{ij},
otherwise. The signing is *symmetric* if for every element (*i,j*) in
I, also (*j,i*) is in I.

**Conjecture (Nati Linial):** If
** A** is the adjacency matrix of a
*d*-regular graph (*d* > 1),
then there is a symmetric signing ** B** of ** A** such that all eigenvalues of
** B** are in
absolute value smaller or equal to 2(*d*-1)^{1/2}.

This conjecture, if true, is tight in the sense that the value of 2(*d*-1)^{1/2}
cannot be improved.

The validity of the conjecture would yield an elementary construction
of Ramanujan graphs.

Bilu and Linial (private communication) have proved that there is a symmetric signing such that all
eigenvalues of the resulting matrix are in abolute value smaller than O(*d*^{1/2} log^{3/2}*d*).

###

### Problem 4 (by Robin Thomas)

**Conjecture (Robin Thomas and Paul Wollan):** Let
k be a positive integer and let G be a 2k-connected graph of order n. If G has
at least (2k-1)n - (3k+1)k/2 + 1 edges, then G is k-linked.

The conjecture has been proved for k = 1,2,3.

**References**

Send comments to Bojan.Mohar@uni-lj.si

##### Revised:
January 31, 2005.