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.
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 Bij = Aij if the pair (i,j) belongs to I, and Bij = - Aij, 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(d1/2 log3/2d).
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
