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: We present an algorithm that determines the prime factors of connected graphs with respect to the Cartesian product in linear time and space. This improves a result of Aurenhammer et al. [Cartesian graph factorization at logarithmic cost per edge, Comput. Complexity 2 (1992) 331–349], who compute the prime factors in time, where m denotes the number of vertices of G and n the number of edges. Our algorithm is conceptually simpler. It gains its efficiency by the introduction of edge-labellings. [Copyright &y& Elsevier]

Abstract: In this paper it is shown that a class of almost-median graphs that includes all planar almost-median graphs can be recognized in time, where n denotes the number of vertices and m the number of edges. Moreover, planar almost-median graphs can be recognized in linear time. As a key auxiliary result we prove that all bipartite outerplanar graphs are isometric subgraphs of the hypercube and that the embedding can be effected in linear time. [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]