IsSubgraphIsomorphic - Maple Help

GraphTheory

 IsSubgraphIsomorphic
 determine if a subgraph isomorphism exists

 Calling Sequence IsSubgraphIsomorphic(G1,G2)

Parameters

 G1, G2 - graphs

Options

 • isomorphism = truefalse
 Specifies whether the isomorphism should be returned when it exists. In this case the result is an expression sequence consisting of true and a set of equations specifying a mapping from the vertices of G1 to those of G2.

Description

 • IsSubgraphIsomorphic(G) accepts either two undirected graphs or two directed graphs as input.  It returns true if G1 is isomorphic to some subgraph of G2.
 • If the graphs are weighted graphs, the edge weights are ignored.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$

An undirected graph example: C6 is isomorphic to a subgraph of K33 but not of K24.

 > $\mathrm{C6}≔\mathrm{CycleGraph}\left(6\right)$
 ${\mathrm{C6}}{≔}{\mathrm{Graph 1: an undirected graph with 6 vertices and 6 edge\left(s\right)}}$ (1)
 > $\mathrm{K24}≔\mathrm{CompleteGraph}\left(2,4\right)$
 ${\mathrm{K24}}{≔}{\mathrm{Graph 2: an undirected graph with 6 vertices and 8 edge\left(s\right)}}$ (2)
 > $\mathrm{K33}≔\mathrm{CompleteGraph}\left(3,3\right)$
 ${\mathrm{K33}}{≔}{\mathrm{Graph 3: an undirected graph with 6 vertices and 9 edge\left(s\right)}}$ (3)
 > $\mathrm{IsSubgraphIsomorphic}\left(\mathrm{C6},\mathrm{K33}\right)$
 ${\mathrm{true}}$ (4)
 > $\mathrm{IsSubgraphIsomorphic}\left(\mathrm{C6},\mathrm{K33},\mathrm{isomorphism}\right)$
 ${\mathrm{true}}{,}\left\{{1}{=}{6}{,}{2}{=}{3}{,}{3}{=}{5}{,}{4}{=}{2}{,}{5}{=}{4}{,}{6}{=}{1}\right\}$ (5)
 > $\mathrm{IsSubgraphIsomorphic}\left(\mathrm{C6},\mathrm{K24}\right)$
 ${\mathrm{false}}$ (6)

Compatibility

 • The GraphTheory[IsSubgraphIsomorphic] command was introduced in Maple 2021.