Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9513251 | Discrete Mathematics | 2005 | 8 Pages |
Abstract
A graph polynomial P(G,x) is called reconstructible if it is uniquely determined by the polynomials of the vertex-deleted subgraphs of G for every graph G with at least three vertices. In this note it is shown that subgraph-counting graph polynomials of increasing families of graphs are reconstructible if and only if each graph from the corresponding defining family is reconstructible from its polynomial deck. In particular, we prove that the cube polynomial is reconstructible. Other reconstructible polynomials are the clique, the path and the independence polynomials. Along the way two new characterizations of hypercubes are obtained.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Boštjan Brešar, Wilfried Imrich, Sandi Klavžar,