GraphTheory[SpecialGraphs] - Maple Help

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

GraphTheory[SpecialGraphs]

 PayleyGraph
 construct Payley graph

 Calling Sequence PayleyGraph(p) PayleyGraph(p,k) PayleyGraph(p,k,m)

Parameters

 p - prime integer k - positive integer m - irreducible univariate polynomial of degree k over GF(p)

Description

 • If the input is PayleyGraph(p) then the output is an undirected unweighted simple graph G on p vertices labeled 0,1,...,p-1 where the edge {i,j}, with i
 • If the input is PayleyGraph(p,k) then the output is an undirected unweighted simple graph G on $q={p}^{k}$ vertices labeled 0,1,...,q-1 where the edge {i,j}, i
 • The vertex label for the element f(x) in Zp[x] is f(p). For example, in GF(23) the elements are ordered $0,1,x,x+1,{x}^{2},{x}^{2}+1,{x}^{2}+x,{x}^{2}+x+1$. Thus the label for element ${x}^{2}+1$ is ${2}^{2}+1=5$.
 • The field can be specified by specifying the extension polynomial by the user by specifying the extension polynomial for GF(q), a monic irreducible polynomial m(x) in Zp[x] of degree k.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$
 > $P≔\mathrm{PayleyGraph}\left(5\right)$
 ${P}{:=}{\mathrm{Graph 1: an undirected unweighted graph with 5 vertices and 5 edge\left(s\right)}}$ (1)
 > $E≔\mathrm{Edges}\left(P\right)$
 ${E}{:=}\left\{\left\{{0}{,}{1}\right\}{,}\left\{{0}{,}{4}\right\}{,}\left\{{1}{,}{2}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{3}{,}{4}\right\}\right\}$ (2)
 > $P≔\mathrm{PayleyGraph}\left(2,2\right)$
 ${P}{:=}{\mathrm{Graph 2: an undirected unweighted graph with 4 vertices and 6 edge\left(s\right)}}$ (3)
 > $E≔\mathrm{Edges}\left(P\right)$
 ${E}{:=}\left\{\left\{{0}{,}{1}\right\}{,}\left\{{0}{,}{2}\right\}{,}\left\{{0}{,}{3}\right\}{,}\left\{{1}{,}{2}\right\}{,}\left\{{1}{,}{3}\right\}{,}\left\{{2}{,}{3}\right\}\right\}$ (4)
 > $P≔\mathrm{PayleyGraph}\left(3,2,{y}^{2}+1\right)$
 ${P}{:=}{\mathrm{Graph 3: an undirected unweighted graph with 9 vertices and 18 edge\left(s\right)}}$ (5)
 > $E≔\mathrm{Edges}\left(P\right):$