 GraphPolynomial - Maple Help

GraphTheory

 GraphPolynomial
 construct graph polynomial Calling Sequence GraphPolynomial(G,x) Parameters

 G - undirected unweighted graph x - name or list(algebraic) Description

 • GraphPolynomial(G,x) returns a polynomial in the variables ${x}_{1}$,...,${x}_{n}$ when x is a symbol and G is a graph with $n$ vertices. The polynomial consists only of linear factors of the form $\left({x}_{j}-{x}_{k}\right)$ where $j$ and $k$ represent adjacent vertices.
 • If x is a list of algebraic expressions whose length is equal to the number of vertices of G, the polynomial is formed using linear factors of the form $\left(x\left[j\right]-x\left[k\right]\right)$ where $j$ and $k$ represent adjacent vertices. Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $G≔\mathrm{Graph}\left(\left[1,2,3,4,5,6\right],\left\{\left\{4,5\right\},\left\{3,4\right\},\left\{4,6\right\},\left\{5,6\right\},\left\{3,5\right\},\left\{1,4\right\},\left\{2,6\right\}\right\}\right):$
 > $\mathrm{GraphPolynomial}\left(G,x\right)$
 $\left({\mathrm{x1}}{-}{\mathrm{x4}}\right){}\left({\mathrm{x2}}{-}{\mathrm{x6}}\right){}\left({\mathrm{x3}}{-}{\mathrm{x4}}\right){}\left({\mathrm{x3}}{-}{\mathrm{x5}}\right){}\left({\mathrm{x4}}{-}{\mathrm{x5}}\right){}\left({\mathrm{x4}}{-}{\mathrm{x6}}\right){}\left({\mathrm{x5}}{-}{\mathrm{x6}}\right)$ (1)
 > $\mathrm{GraphPolynomial}\left(\mathrm{CycleGraph}\left(4\right),\left[x,y,z,w\right]\right)$
 $\left({x}{-}{y}\right){}\left({x}{-}{w}\right){}\left({y}{-}{z}\right){}\left({z}{-}{w}\right)$ (2) References

 Noga Alon and Michael Tarsi, "A note on graph colorings and graph polynomials", J. Combin. Theory Ser. B 70 (1997), no. 1, 197–201, doi: 10.1006/jctb.1997.1753 Compatibility

 • The GraphTheory[GraphPolynomial] command was updated in Maple 2019.