Skip to main content
1 of 2
H A Helfgott
  • 20.2k
  • 3
  • 43
  • 126

Closed paths, traces and spectra

Let $\Gamma$ be a graph. Write $A$ for its adjacency matrix. It is trivial to show that $\mathrm{Tr} A^k$ equals the number of closed walks of length k, that is, the number of $k$-step walks that return to where they started.

Suppose that we show that $\Gamma$ has few closed paths of length $\leq k$. (A path is a walk without repeated vertices; obviously we are allowing (and requiring) the origin vertex to be the ending vertex.) Can we prove an upper bound on $\mathrm{Tr} A^k$ as a result? If not, can we prove something else about the spectrum of $A$, possibly with additional conditions?

(The same questions can be posed if we show that $\Gamma$ has few closed trails of length $\leq k$. A trail is a walk without repeated edges.)

H A Helfgott
  • 20.2k
  • 3
  • 43
  • 126