Paper detail

Subgraph posets and graph reconstruction

We consider 3 (weighted) posets associated with a graph G - the poset P(G) of distinct induced unlabelled subgraphs, the lattice Omega(G) of distinct unlabelled graphs induced by connected partitions, and the poset Q(G) of distinct unlabelled edge-subgraphs. We study these posets given up to isomorphism, and their relation to the reconstruction conjectures. We show that when G is not a star or a disjoint union of edges, P(G) and Omega(G) can be constructed from each other. The result implies that trees are reconstructible from their abstract bond lattice. We present many results on the reconstruction questions about the chromatic symmetric function and the symmetric Tutte polynomial. In particular, we show that the symmetric Tutte polynomial of a tree can be constructed from its chromatic symmetric function. We classify graphs that are not reconstructible from their abstract edge-subgraph posets, and further show that the families presented here are the only graphs not Q-reconstructible if and only if the edge reconstruction conjecture is true. Let f be a bijection from the set of all unlabelled graphs to itself such that for all unlabelled graphs G and H, hom(G,H) = hom(f(G), f(H)). We conjecture that f is an identity map. We show that this conjecture is weaker than the edge reconstruction conjecture. Our conjecture is motivated by homomorphism cancellation results due to Lovász.