Roots of cube polynomials of median graphs

✍ Scribed by Boštjan Brešar; Sandi Klavžar; Riste Škrekovski

• Publisher: John Wiley and Sons
• Year: 2006
• Tongue: English
• Weight: 122 KB
• Volume: 52
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20146

✦ Synopsis

Abstract

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