School Seminars and Colloquia

The number of labeled connected graphs on $n$ vertices modulo a prime power

Discrete Structures and Algorithms (Seminar)

by Arun Mani

Institution: The University of Melbourne
Date: Wed 10th April 2013
Time: 2:30 PM
Location: Old Geology Theatre 2

Abstract: We will state and prove some recurrent congruences for the sequence $(c(n) : n \mbox{ a positive integer})$, where $c(n)$ denotes the number of labeled connected graphs on $n$ vertices. In particular, for an odd prime $p$ and positive integers $n$ and $k$, we will show $c(n+p^k) \equiv 2^{(p^k - p^{k-1})/2} c(n+p^{k-1})~ {\rm mod}~{p^k}$. This is joint work with Douglas Stones (Dalhousie University, Canada).