5
$\begingroup$

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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
5
$\begingroup$
  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.
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .