Macaulay2 » Documentation
Packages » EdgeIdeals :: inducedGraph
next | previous | forward | backward | up | index | toc

inducedGraph -- returns the induced subgraph of a graph

Synopsis

Description

This function returns the induced subgraph of a graph on a specified set of vertices. This function enables the user to create subgraphs of the original graph. inducedGraph accepts a Graph as input and returns a Graph as well. Use inducedHyperGraph for a HyperGraph instead.

The default option is for the ring of the induced subgraph to contain only variables in L. Then the current ring must be changed before working with the induced subgraph. We use this setup to avoid having a lot of isolated vertices in the induced graph. However, one can set the option OriginalRing to true if one wants to give the induced graph the same ring as the original graph.

i1 : R = QQ[a,b,c,d,e];
 
i2 : G = graph {a*b,b*c,c*d,d*e,e*a} -- graph of the 5-cycle

o2 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {a, e}, {d, e}}}
           "ring" => R
           "vertices" => {a, b, c, d, e}

o2 : Graph
 
i3 : H1 = inducedGraph(G,{b,c,d,e})

o3 = Graph{"edges" => {{b, c}, {c, d}, {d, e}}}
           "ring" => QQ[b..e]
           "vertices" => {b, c, d, e}

o3 : Graph
 
i4 : H2 = inducedGraph(G,{a,b,d,e})

o4 = Graph{"edges" => {{a, b}, {a, e}, {d, e}}}
           "ring" => QQ[a..b, d..e]
           "vertices" => {a, b, d, e}

o4 : Graph
 
i5 : use ring H1

o5 = QQ[b..e]

o5 : PolynomialRing
 
i6 : inducedGraph(H1,{c,d,e})

o6 = Graph{"edges" => {{c, d}, {d, e}}}
           "ring" => QQ[c..e]
           "vertices" => {c, d, e}

o6 : Graph
 
i7 : use ring G

o7 = R

o7 : PolynomialRing
 
i8 : inducedGraph(G,{b,c,d,e},OriginalRing=>true) --H1 but in bigger ring

o8 = Graph{"edges" => {{b, c}, {c, d}, {d, e}}}
           "ring" => R
           "vertices" => {a, b, c, d, e}

o8 : Graph

Equivalently, one can use changeRing (and graph) to move the induced graph back into the original ring.

i9 : R = QQ[a,b,c,d,e];
 
i10 : G = graph {a*b,b*c,c*d,d*e,e*a} -- graph of the 5-cycle

o10 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {a, e}, {d, e}}}
            "ring" => R
            "vertices" => {a, b, c, d, e}

o10 : Graph
 
i11 : H = inducedGraph(G,{b,c,d})

o11 = Graph{"edges" => {{b, c}, {c, d}}}
            "ring" => QQ[b..d]
            "vertices" => {b, c, d}

o11 : Graph
 
i12 : graph changeRing(H,R,{b,c,d})

o12 = Graph{"edges" => {{c, d}, {b, c}}  }
            "ring" => R
            "vertices" => {a, b, c, d, e}

o12 : Graph

See also

Ways to use inducedGraph :

For the programmer

The object inducedGraph is a method function with options.