Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
1. I guess it should be community wiki. 2. A bit vague... 3. Nevertheless, I'll post an answer :) –  Felix Goldberg May 10 '12 at 21:08
add comment

2 Answers

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.

share|improve this answer
add comment
  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.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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