Roots of cube polynomials of median graphs

The cube polynomial c ( G , x ) of a graph G is defined as $\sum\nolimits_{i \ge 0} {\alpha _i ( G)x^i }$ , where α i ( G ) denotes the number of induced i ‐cubes of G , in particular, α 0 ( G ) = | V ( G )| and α 1 ( G ) = | E ( G )|. Let G be a median graph. It is proved that every rational zero of c ( G , x ) is of the form −(( t  + 1)/ t for some integer t  > 0 and that c ( G , x ) always has a real zero in the interval [−2,−1). Moreover, c ( G , x ) has a p ‐multiple zero if and only if G is the Cartesian product of p trees all of the same order. Graphs of acyclic cubical complexes are characterized as the graphs G for which c ( H , −2) = 0 holds for every 2‐connected convex subgraph H of G . Median graphs that are Cartesian products are also characterized. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 37–50, 2006