GraphTheory - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/GraphPolynomial

GraphTheory

 GraphPolynomial

 Calling Sequence GraphPolynomial(G,x)

Parameters

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

Description

 • The GraphPolynomial command returns a polynomial in the variables $\mathrm{x1}$,...,$\mathrm{xn}$ when x is a symbol and G is a graph with $n$ vertices. The polynomial consists only of linear factors of the form ($\mathrm{xj}$-$\mathrm{xk}$) 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 (${x}_{j}$-${x}_{k}$) 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\{1,4\right\},\left\{2,6\right\},\left\{3,4\right\},\left\{3,5\right\},\left\{4,5\right\},\left\{4,6\right\},\left\{5,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.