TOPICS
Search

Cube Polynomial

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The cube polynomial, perhaps more explicitly called the hypercube polynomial, of a graph G is a polynomial

C_G(x)=sum_(k=1)^nc_k(G)x^k,

which encodes the numbers c_k(G) of vertex-induced subgraphs of G that are isomorphic to the hypercube graph Q_k.

For any graph G, c_0(G) is simply the vertex count |V(G)| and c_1(G) is the edge count |E(G)|.

See also

Connected Induced Subgraph Polynomial, Hypercube Graph, Vertex-Induced Subgraph

Explore with Wolfram|Alpha

References

Brešar, B.; Klavžar, S.; and Škrekovski, R. "The Cube Polynomial and Its Derivatives: The Case of Median Graphs." Elec. J. Combin. 10, R3, 2003. https://doi.org/10.37236/1696.Klavžar, S. and Mollard, M. "Cube Polynomial of Fibonacci and Lucas Cubes." Acta Appl. Math. 117, 93-105, 2012.Xie, Y.-T.; Feng, Y.-D.; and Xu, S.-J. "A Relation between the Cube Polynomials of Partial Cubes and the Clique Polynomials of Their Crossing Graphs." 26 Mar 2023. https://arxiv.org/abs/2303.14671.

Cite this as:

Weisstein, Eric W. "Cube Polynomial." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CubePolynomial.html

Subject classifications