GraphTheory/IsRamanujanGraph - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Home : Support : Online Help : GraphTheory/IsRamanujanGraph

GraphTheory

 IsRamanujanGraph
 test if graph is Ramanujan

 Calling Sequence IsRamanujanGraph(G,opts)

Parameters

 G - graph opts - (optional) equation of the form parameters=true or parameters=false

Options

 • parameters : keyword option of the form parameters=true or parameters=false. This specifies whether the parameters [d, lambda] should be returned when the graph is Ramanujan. The default is false.

Description

 • The IsRamanujanGraph(G) command returns true if G is a Ramanujan graph and false otherwise.

Definition

 • An undirected graph G is Ramanujan if it is a regular graph with degree d and $\mathrm{lambda}\le 2\sqrt{d-1}$, where $\mathrm{lambda}$ is the maximum of the absolute values of all the eigenvalues of the adjacency matrix of G excluding the greatest eigenvalue d.
 • These graphs are named after Srinivasa Ramanujan.

Ramanujan graphs in SpecialGraphs

 • The following are graphs in the SpecialGraphs subpackage which are Ramanujan.

 Graph Number of Vertices d lambda 10 3 3 12 5 sqrt(5) 16 5 3 d d-1 1 p (q-1)/2 (sqrt(q)+1)/2

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$
 > $G≔\mathrm{Graph}\left(\left\{\left\{1,2\right\},\left\{1,3\right\},\left\{2,3\right\},\left\{3,4\right\}\right\}\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected graph with 4 vertices and 4 edge\left(s\right)}}$ (1)
 > $\mathrm{IsRamanujanGraph}\left(G\right)$
 ${\mathrm{false}}$ (2)
 > $P≔\mathrm{PetersenGraph}\left(\right)$
 ${P}{≔}{\mathrm{Graph 2: an undirected graph with 10 vertices and 15 edge\left(s\right)}}$ (3)
 > $\mathrm{IsRamanujanGraph}\left(P,'\mathrm{parameters}'\right)$
 ${\mathrm{true}}{,}\left[{3}{,}{2.000000000}\right]$ (4)
 > $P≔\mathrm{PaleyGraph}\left(29\right)$
 ${P}{≔}{\mathrm{Graph 3: an undirected graph with 29 vertices and 203 edge\left(s\right)}}$ (5)
 > $\mathrm{IsRamanujanGraph}\left(P,'\mathrm{parameters}'\right)$
 ${\mathrm{true}}{,}\left[{14}{,}{3.192582400}\right]$ (6)
 > $C≔\mathrm{ClebschGraph}\left(\right)$
 ${C}{≔}{\mathrm{Graph 4: an undirected graph with 16 vertices and 40 edge\left(s\right)}}$ (7)
 > $\mathrm{IsRamanujanGraph}\left(C,'\mathrm{parameters}'\right)$
 ${\mathrm{true}}{,}\left[{5}{,}{3.000000000}\right]$ (8)

Compatibility

 • The GraphTheory[IsRamanujanGraph] command was introduced in Maple 2023.
 • For more information on Maple 2023 changes, see Updates in Maple 2023.