Originator: Sebastian Cioabă (presented by Sebastian Cioabă - REGS 2011)
Definitions: The eigenvalues of a graph are the eigenvalues of its adjacency matrix. For an $n$-vertex graph, the adjacency matrix $A$ is real and symmetric, and hence the eigenvalues are real and are indexed as $\lambda_1,\ldots,\lambda_n$ in nonincreasing order. The spectrum is the multiset of these eigenvalues. A $(v,k,\lambda,\mu)$-strongly regular graph (SRG) is a $k$-regular graph with $v$ vertices such that any two adjacent vertices have exactly $\lambda$ common neighbors and any two non-adjacent vertices have exactly $\mu$ common neighbors.
Background: One goal of spectral graph theory is to find connections between algebraic invariants of a graph $G$ such as its eigenvalues and combinatorial parameters of $G$ such as its expansion number, diameter, connectivity, chromatic number, independence number, matching number etc. (see [Bi,BH,Ch,CRS,GoAC93,Go1,GR,vLW] for more details). For example, a graph is bipartite if and only the spectrum of its adjacency matrix is symmetric with respect to $0$, and an $n$-vertex graph is regular if and only if $n\lambda_1=\sum_{i=1}^{n}\lambda_i^2$. Also, the largest eigenvalue of a $k$-regular graph is $k$, and the multiplicity of $k$ as an eigenvalue is the number of components.
Small examples of strongly regular graphs include $C_4$ (parameters $(4,2,0,2)$), $C_5$ (parameters $(5,2,0,1)$), and the Petersen graph (parameters $(10,3,0,1)$). Infinite families of strongly regular graphs include the Paley graphs; when $q$ is a prime congruent to $1$ modulo $4$, the Paley graph has vertex set $\mathbb{F}_q-\{0\}$, with vertices $x$ and $y$ adjacent if and only if $x-y$ is a nonzero square in $\mathbb{F}_q$. The Paley graph is strongly regular with parameters $\left(q-1,\frac{q-1}{2},\frac{q-5}{4},\frac{q-1}{4}\right)$). The line graph of $K_m$ is strongly regular with parameters $\left({m\choose 2}, 2(m-2), m-2,4\right)$. The line graph of $K_{m,m}$ is strongly regular with parameters $\left(m^2,2(m-1),m-2,2\right)$. For other examples, see Brouwer-Haemers [BH], Godsil-Royle [GR], van Lint-Wilson [vLW]); these graphs are interesting objects related to algebra, geometry, and coding theory.
If $G$ is strongly regular with parameters $(v,k,\lambda,\mu)$, then $A^2=kI+\lambda A+\mu(J-I-A)$, where $A$ is the adjacency matrix and $J$ is the all-$1$ matrix (compare corresponding entries). When $G$ is strongly regular and is not a disjoint union of copies of $K_{k+1}$, this equation implies that $G$ has three distinct eigenvalues. The eigenvalues are $k$, $\theta$, and $\tau$, where $\theta$ and $\tau$ are solutions of $x^2-(\lambda-\mu)x+(\mu-k)=0$. One can express these eigenvalues and their multiplicities in terms of $v$, $k$, $\lambda$, and $\mu$.
A graph with maximum degree $k$ having diameter $2$ and $k^2+1$ vertices must have girth $5$ and be strongly regular with parameters $(k^2+1,k,0,1)$. An early application of eigenvalue methods by Hoffman and Singleton [1960] showed that $k\in \{2,3,7,57\}$; the argument uses that the multiplicity of the eigenvalue $\theta$ is an integer. In the first three cases, $G$ is $C_5$, the Petersen graph, or the Hoffman-Singleton graph (a $7$-regular graph with $50$ vertices). After 50 years, it is still not known whether a $57$-regular construction exists ($3250$ vertices).
Schwenk (see [BH,GR] for more details) applied eigenvalues to forbid the decomposition of $K_{10}$ into three copies of the Petersen graph. If such a decomposition exists, then let the adjacency matrices of the subgraphs be $A_1,A_2,A_3$ relative to a fixed indexing of $V(K_{10})$. Thus, $A(K_{10})=A_1+A_2+A_3$. The Petersen graph has spectrum $(3^{(1)},1^{(5)},-2^{(4)})$, where the exponent denotes the multiplicity. The eigenvector for eigenvalue $3$ is the constant vector; all other eigenvectors are in the $9$-dimensional orthogonal complement of the $1$-dimensional subspace spanned by the constant vectors. For $i\in\{1,2,3\}$, let $V_i$ be the $5$-dimensional space of eigenvectors with eigenvalue $1$ for the $i$th subgraph. Since they are contained in a $9$-dimensional space, there is a nonzero vector $x$ such that $A_1x=A_2x=x$. It follows that $A(K_{10})x=(A_1+A_2+A_3)x=2x+A_3x$. Since $x$ is orthogonal to constant vectors, the spectrum of the complete graph yields $A(K_10)x=-x$. We conclude that $A_3x=-3x$, so $-3$ is an eigenvalue of the Petersen graph, which is a contradiction.
Problem 1: Can the edges of the multigraph $3K_{10}$ (multiplicity $3$ for each edge) be partitioned into nine copies of the Petersen graphs?
Comments: Randy Elzinga has a construction showing that $2K_{10}$ can be partitioned into $6$ Petersen graphs. Edwin van Dam had asked whether this was possible.
Problem 2: Does $2K_{55}$ decompose into six copies of the line graph of $K_{11}$?
Comments: An argument like that of Schwenk shows that $K_{55}$ cannot be partitioned into three copies of $L(K_{11})$.
Problem 3: Let $G$ be strongly regular, and suppose that $G$ and $\overline{G}$ are connected. In terms of the parameters $(v,k,\lambda,\mu)$ of $G$, what are the possible values of the connectivity or edge-connectivity of the subgraph induced by the vertices at distance $2$ from a fixed vertex $u$ (also called the second subconstituent of $u$) ?
Comments: Eigenvalue methods show that for a strongly regular graph such that $G$ and $\overline G$ are connected, the vertices at distance $2$ from a fixed vertex induce a connected regular subgraph with degree $k-\mu$ (see [BH] for the details). Brouwer and Haemers [BH] constructed an example where the connectivity of the second subconstituent is strictly less than $k-\mu$. It is known that the connectivity of a strongly regular graph equals its degree (this was proved by Brouwer and Mesner using eigenvalue methods; see [BH] for a short proof).
References:
[Bi] N. Biggs, Algebraic Graph Theory, 2nd Edition.
[BH] A.E. Brouwer and W.H. Haemers, Spectra of graphs, 210pp
monograph (2011), available at http://homepages.cwi.nl/~aeb/math/ipm.pdf.
[Ch] F. Chung, Spectral Graph Theory.
[CRS] Dragos Cvetkovic, Peter Rowlinson, and Slobodan Simic,
Eigenspaces of Graphs, Cambridge University Press, Cambridge, UK.
[GoAC93] C.D. Godsil, Algebraic combinatorics. Chapman and Hall
Mathematics Series. Chapman & Hall, New York, 1993.
[Go1] C. Godsil, Tools from linear algebra, With an appendix by
L. Lovász. Handbook of combinatorics, Vol. 1, 2,
1705-1748, Elsevier, Amsterdam, (1995).
[GR] C. Godsil and G. Royle, Algebraic Graph Theory,
Springer 2001.
[vLW] J. van Lint and R.M. Wilson, A Course in Combinatorics, Second
Edition, Cambridge University Press, Cambridge, (2001). xiv+602 pp.