I have a heavily symmetric regular graph whose automorphisms I know. I remove one subgraph and insert another one in a consistent manner; for example, this could be a Delta-Y transformation ...
Actually, I suppose that the answer is technically "yes," since computing the permanent is #P-complete, but that's not very satisfying. So here's what I mean: Kirchhoff's theorem says that if you ...
Pretty much exactly what it says on the tin. Let G be a connected graph; then the Tutte polynomial T_G(x,y) carries a lot of information about G. However, it obviously doesn't encode everything about ...
Erdős's 1947 probabilistic trick provided a lower exponential bound for the Ramsey number R(k). Is it possible to explicitly construct 2-colourings on exponentially sized graphs without large ...