Search

Abstract: We show that regular median graphs of linear growth are the Cartesian product of finite hypercubes with the two-way infinite path. Such graphs are Cayley graphs and have only two ends. For cubic median graphs the condition of linear growth can be weakened to the condition that has two ends. For higher degree the relaxation to two-ended graphs is not possible, which we demonstrate by an example of a median graph of degree four that has two ends, but nonlinear growth. [Copyright &y& Elsevier]

Abstract: A graph polynomial 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. [Copyright &y& Elsevier]