Studying algebraic graph theory, I've stumbled across a wide range of results that I found pretty stunning and also useful. I'd like to share them here and ask for your favorite result from this area?

Let $G$ be a simple graph $A$ and $L$ its adjacency and Laplacian matrix $\lambda_1\leq \cdots \leq\lambda_n$ and $\mu_1 \leq \cdots \leq \mu_n$ the respective eigenvalues of $A$ and $L$.

  1. (Wilf, Hoffman) For a nontrivial graph $G$ $$1+\frac{\lambda_n}{-\lambda_1} \leq \chi(G) \leq 1+\lambda_n$$

  2. (Sachs,Harary) Let $G$ be a graph of odd girth $2r+1.$ Let $p(x) = \sum_{i=0}^n c_{n-i} x^i$ be the characteristic polynomial of $A.$ Then $$c_3 = \cdots = c_{2r-1} = 0$$ and $\frac{-c_{2r+1}}{2}$ is the number of $(2r+1)$-cycles in G.

  3. (Folklore) The number of triangles in $G$ equals $tr(A^3)/6.$ Since matrix multiplication can be done in $O(n^k)$ for $k \leq 2.37$ this presents an improvement over the straightforward approach for counting triangles in graphs that is currently the fastest way to compute the number of triangles in simple graphs.

  4. (Kirchhoff) The number of spanning trees in G is $\frac{1}{n}\mu_2 \cdots \mu_n$

  5. (McKay) $diam(G) \geq \frac{4}{n\mu_2}$

Do you have any neat results like this to share?


I have incorporated some results I like in algebraic graph theory into my notes http://math.mit.edu/~rstan/algcomb.pdf. See for instance Example 9.12 (number of spanning trees of the $n$-cube), Corollary 10.11 (enumeration of binary de Bruijn sequences), Section 11.5 (squaring the square), Section 12.3 (complete bipartite partitions of $K_n$), and Section 12.5 (odd neighborhood covers). Many other nice examples are in Matoušek's Thirty-three Miniatures.

  • 1
    $\begingroup$ The link is not working. $\endgroup$
    – Anurag
    Mar 28 '15 at 13:42
  1. $A^{k}_{ij}$ counts the $k$-paths from $i$ to $j$. This is what got me hooked on algebraic graph theory in the first place.
  2. Fielder's algebraic connectivity <= vertex connectivity.
  3. The relations between vertex connectivity and isoperimetric number.
  4. Lovasz's bound on Shannon capacity.
  5. The classification of generalized line graphs.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.