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

GraphTheory

 IdentifyGraph
 search for isomorphism to named graphs

 Calling Sequence IdentifyGraph(G)

Parameters

 G - graph

Description

 • IdentifyGraph takes as input an unweighted graph G and attempts to find isomorphisms to one or more named graphs known to GraphTheory.

Examples

The cycle graph on 5 vertices is also the Paley graph on 5 vertices, and this will appear in the list of results.

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $G≔\mathrm{CycleGraph}\left(5\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected graph with 5 vertices and 5 edge\left(s\right)}}$ (1)
 > $\mathrm{IdentifyGraph}\left(G\right)$
 $\left[\left[{\mathrm{CycleGraph}}{,}{5}\right]{,}\left[{\mathrm{SpecialGraphs}}{:-}{\mathrm{CageGraph}}{,}{2}{,}{5}\right]{,}\left[{\mathrm{SpecialGraphs}}{:-}{\mathrm{PaleyGraph}}{,}{5}\right]\right]$ (2)

In this example we begin by picking any edge {a,b} from the Hoffman-Singleton graph and deleting all vertices incident to a or b.

 > $\mathrm{HS}≔\mathrm{SpecialGraphs}:-\mathrm{HoffmanSingletonGraph}\left(\right)$
 ${\mathrm{HS}}{≔}{\mathrm{Graph 2: an undirected graph with 50 vertices and 175 edge\left(s\right)}}$ (3)
 > $\mathrm{edge}≔{\mathrm{Edges}\left(\mathrm{HS}\right)}_{100}$
 ${\mathrm{edge}}{≔}\left\{{20}{,}{25}\right\}$ (4)
 > $G≔\mathrm{DeleteVertex}\left(\mathrm{HS},\mathrm{convert}\left(\mathrm{Neighborhood}\left(\mathrm{HS},{\mathrm{edge}}_{1}\right),\mathrm{set}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}∪\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{convert}\left(\mathrm{Neighborhood}\left(\mathrm{HS},{\mathrm{edge}}_{2}\right),\mathrm{set}\right)\right)$
 ${G}{≔}{\mathrm{Graph 3: an undirected graph with 36 vertices and 90 edge\left(s\right)}}$ (5)

With IdentifyGraph, we discover that this subgraph has a name: it is isomorphic to the Sylvester graph.

 > $\mathrm{IdentifyGraph}\left(G\right)$
 $\left[\left[{\mathrm{SpecialGraphs}}{:-}{\mathrm{SylvesterGraph}}\right]\right]$ (6)

Compatibility

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