Subgraph posets, partition lattices, graph polynomials and reconstruction

Details Subgraph posets, partition lattices, graph polynomials and reconstruction Subgraph posets, partition lattices, graph polynomials and reconstruction

2006-09-20

arxiv.org/abs/math/0609574v1

Mathematics

Combinatorics

36 pages, 8 figures

Scientific paper

This paper deals with crtain posets and lattices associated with a graph. In my earlier paper I showed that several invariants of a graph can be computed from the isomorphism class of its poset of non-empty induced subgraphs. In this paper I will prove that the (abstract and folded) connected partition lattice of a graph can be constructed from its abstract poset of induced subgraphs. I will also prove that, except when the graph is a star or a disjoint union of edges, the abstract induced subgraph poset of the graph can be constructed from its abstract folded connected partition lattice. The chromatic symmetric function and the symmetric Tutte polynomial are proved to be reconstructible. The second construction implies that a tree can be reconstructed from the isomorphism class of its folded connected partition lattice. I then show that the symmetric Tutte polynomial of a tree can be computed from the chromatic symmetric function of the tree, thus showing that a question of Noble and Welsh is equivalent to Stanley's question about the chromatic symmetric function of trees. The paper also develops edge reconstruction theory on the edge subgraph poset, and its relation with Lov\'asz's homomorphism cancellation laws. A characterisation of a family of graphs that cannot be constructed from their abstract edge subgraph posets is also presented.

Affiliated with

Also associated with

No associations

Rating

Subgraph posets, partition lattices, graph polynomials and reconstruction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Subgraph posets, partition lattices, graph polynomials and reconstruction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Subgraph posets, partition lattices, graph polynomials and reconstruction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-351550