# Graphs

## Authors

• Jack Burkart
• David Cook II
• Caroline Jansen
• Amelia Taylor
• Augustine O'Keefe
• Contributors of note: Carlos Amendola, Alex Diaz, Luis David Garcia Puente, Roser Homs Pons, Olga Kuznetsova, Shaowei Lin, Sonja Mapes, Harshit J Motwani, Mike Stillman, Doug Torrance

## Version

This documentation describes version 0.3.3 of Graphs.

## Source code

The source code from which this documentation is derived is in the file Graphs.m2.

## Exports

• Types
• Functions and commands
• addVertex -- A method for adding a set of vertices to a graph
• "addVertices" -- see addVertex -- A method for adding a set of vertices to a graph
• adjacencyMatrix -- Returns the adjacency matrix of a Graph or Digraph
• barbellGraph -- Returns the barbell graph
• barycenter -- Returns the barycenter of a grah
• BFS (missing documentation)
• bipartiteColoring -- Returns a coloring of a bipartite graph
• breadthFirstSearch -- runs a breadth first search on the digraph starting at a specified node and returns a list of the vertices in the order they were discovered
• cartesianProduct -- Computes the cartesian product of two graphs
• center -- Returns the center of a graph
• children -- returns the children of a vertex of a digraph
• chromaticNumber -- Computes the chromatic number of a graph
• cliqueComplex -- Returns the clique complex of a graph
• cliqueNumber -- Returns the clique number of a graph
• closedNeighborhood -- Returns the closed neighborhood of a vertex of a graph
• clusteringCoefficient (missing documentation)
• cocktailParty -- Returns a cocktail party graph
• complementGraph -- Returns the complement of a graph
• completeGraph -- Constructs a complete graph
• completeMultipartiteGraph -- constructs a complete multipartite graph
• connectedComponents -- Computes the connected components of a graph
• coverIdeal -- Returns the vertex cover ideal of a graph
• criticalEdges -- Finds the critical edges of a graph
• crownGraph -- Returns a crown graph
• cycleGraph -- Constructs a cycle graph
• degeneracy -- Computes the degeneracy of a graph
• degreeCentrality -- Returns the degreeCentrality of a vertex of a graph
• degreeIn -- returns the "in-degree" of a vertex in a digraph
• degreeMatrix -- Returns the degree matrix of a graph
• degreeOut -- returns the "out-degree" of a vertex in a digraph
• deleteEdges -- Deletes a list of edges from a graph
• deleteVertex -- a method for deleting the vertex of a graph
• deleteVertices -- Deletes specified vertices from a digraph or graph
• density -- computes the density of a graph
• depthFirstSearch -- runs a depth first search on the digraph or digraph and returns the discovery time and finishing time for each vertex in the digraph
• descendants -- returns the descendants of a digraph
• descendents (missing documentation)
• DFS (missing documentation)
• diameter -- Computes the diameter of a graph
• digraph -- Constructs a digraph
• digraphTranspose -- returns the transpose of a Digraph
• directProduct -- Computes the direct product of two graphs
• disjointUnion -- Returns the disjoint union of a list of graphs.
• displayGraph -- displays a digraph or graph using Graphviz
• distance -- Computes the distance between two vertexSet in a graph
• distanceMatrix -- Computes the distance matrix of a digraph
• doubleStar -- returns a double star graph
• eccentricity -- Returns the eccentricity of a vertex of a graph
• edgeConnectivity -- computes the edge connectivity of a graph
• edgeCuts -- returns the edge cuts of a graph
• edgeIdeal -- returns the edge ideal of a graph
• edges -- Returns the edges of a digraph or graph
• expansion -- returns the expansion of a graph
• findPaths -- finds all the paths in a digraph of a given length starting at a given vertex
• floydWarshall -- runs the Floyd-Warshall algorithm on a digraph to determine the minimum distance from one vertex to another in the digraph
• foreFathers (missing documentation)
• forefathers -- returns the forefathers of a digrah
• friendshipGraph -- Returns a friendship Graph
• generalizedPetersenGraph -- Returns a generalized petersen graph
• girth -- A method for computing the girth of a graph
• graph -- Constructs a simple graph
• graphComposition -- A method for composing two graphs
• graphLibrary -- constructs a graph of a type specified in the string input
• graphPower -- constructs a graph raised to a power
• hasEulerianTrail -- determines whether a graph or a digraph has an Eulerian trail
• hasOddHole -- checks whether a graph has a odd hole
• incidenceMatrix -- computes the incidence matrix of a graph
• independenceComplex -- constructs the independence complex of a graph
• independenceNumber -- computes the independence number of a graph
• indexLabelGraph -- Relabels the vertices of a graph or digraph according to their indices, indexed from 0.
• inducedSubgraph -- A method for finding the induced subgraph of any Graph or Digraph
• isBipartite -- determines whether a graph is bipartite
• isChordal -- checks whether a graph is chordal
• isCM -- determines if a graph is Cohen-Macaulay
• isConnected -- determines whether a graph is connected
• isCyclic -- determines whether a graph is cyclic
• isEulerian -- determines if a graph or digraph is Eulerian
• isForest -- determines whether a graph is a forest
• isLeaf -- determines whether a vertex is a leaf
• isPerfect -- checks whether a graph is perfect
• isReachable -- checks if a vertex u is reachable from a vertex v
• isRegular -- determines whether a graph is regular
• isRigid -- checks if a graph is rigid
• isSimple -- checks if a graph is simple
• isSink -- determines if a vertex of a digraph is a sink or not
• isSource -- determines if a vertex of a digraph is a source or not
• isStronglyConnected -- checks if a digraph is strongly connected
• isTree -- determines whether a graph is a tree
• isWeaklyConnected -- checks if a digraph is weakly connected
• kneserGraph -- constructs a kneser graph of specified size
• laplacianMatrix -- Returns the laplacian matrix of a graph
• leaves -- lists the leaves of a tree graph
• lexicographicProduct (missing documentation)
• lineGraph -- Returns the line graph of an undirected graph
• lollipopGraph -- constructs a lollipop graph
• lowestCommonAncestors -- determines the lowest common ancestors between two vertexSet
• minimalDegree -- computes the minimal degree of a graph
• minimalVertexCuts -- finds the minimal vertex cuts of a graph
• monomialGraph -- Returns a monomial graph
• neighbors -- returns the neighbors of a vertex in a graph
• nondescendants -- returns the nondescendants of a vertex of a digraph
• nondescendents (missing documentation)
• nonneighbors -- returns the non-neighbors of a vertex in a graph
• numberOfComponents -- computes the number of connected components of a graph
• numberOfTriangles -- counts how many subtriangles are present in a graph
• parents -- returns the parents of a vertex on a digraph
• pathGraph -- A method that makes a path graph
• prismGraph (missing documentation)
• rattleGraph -- Returns a rattle graph
• reachable -- Returns the vertices reachable in a digraph from a given collection of vertices
• reindexBy -- reindexes the vertices according to the input ordering.
• removeNodes (missing documentation)
• reverseBreadthFirstSearch -- runs a reverse breadth first search on the digraph and returns a list of the vertexSet in the order they were discovered
• showTikZ -- Writes a string of TikZ syntax that can be pasted into a .tex file to display G
• sinks -- returns the sinks of a digraph
• sources -- returns the sources of a digraph
• spanningForest -- constructs a spanning forest of a graph
• spectrum -- Returns the spectrum of a graph
• starGraph -- Returns a star graph
• strongProduct -- a method for taking the strong product of two graphs
• tensorProduct (missing documentation)
• thresholdGraph -- A method that generates a threshold graph from a binary list
• topologicalSort -- outputs a list of vertices in a topologically sorted order of a DAG.
• topSort -- outputs a hashtable containing original digraph, new digraph with vertices topologically sorted and a map from vertices of original digraph to new digraph.
• underlyingGraph -- Returns the underlying graph of a digraph
• vertexConnectivity -- computes the vertex connectivity of a graph
• vertexCoverNumber -- returns the vertex cover number of a graph
• vertexCovers -- returns a list of the minimal vertex covers of a graph
• vertexCuts -- lists all the vertex cuts of a graph
• vertexMultiplication
• vertexSet -- Returns the vertices of a graph or digraph
• wheelGraph -- Constructs a wheel graph
• windmillGraph -- Constructs a windmill graph
• writeDotFile -- Writes a graph to a dot file with a specified filename
• Methods
• "addVertex(Digraph,Thing)" -- see addVertex -- A method for adding a set of vertices to a graph
• "addVertices(Digraph,List)" -- see addVertex -- A method for adding a set of vertices to a graph
• "barbellGraph(ZZ)" -- see barbellGraph -- Returns the barbell graph
• "barycenter(Graph)" -- see barycenter -- Returns the barycenter of a grah
• "bipartiteColoring(Graph)" -- see bipartiteColoring -- Returns a coloring of a bipartite graph
• "breadthFirstSearch(Digraph,Thing)" -- see breadthFirstSearch -- runs a breadth first search on the digraph starting at a specified node and returns a list of the vertices in the order they were discovered
• "cartesianProduct(Graph,Graph)" -- see cartesianProduct -- Computes the cartesian product of two graphs
• "center(Graph)" -- see center -- Returns the center of a graph
• "children(Digraph,Thing)" -- see children -- returns the children of a vertex of a digraph
• "chromaticNumber(Graph)" -- see chromaticNumber -- Computes the chromatic number of a graph
• "cliqueComplex(Graph)" -- see cliqueComplex -- Returns the clique complex of a graph
• "cliqueNumber(Graph)" -- see cliqueNumber -- Returns the clique number of a graph
• "closedNeighborhood(Graph,Thing)" -- see closedNeighborhood -- Returns the closed neighborhood of a vertex of a graph
• "cocktailParty(ZZ)" -- see cocktailParty -- Returns a cocktail party graph
• "complementGraph(Graph)" -- see complementGraph -- Returns the complement of a graph
• "completeGraph(ZZ)" -- see completeGraph -- Constructs a complete graph
• "completeMultipartiteGraph(List)" -- see completeMultipartiteGraph -- constructs a complete multipartite graph
• "connectedComponents(Graph)" -- see connectedComponents -- Computes the connected components of a graph
• "coverIdeal(Graph)" -- see coverIdeal -- Returns the vertex cover ideal of a graph
• "criticalEdges(Graph)" -- see criticalEdges -- Finds the critical edges of a graph
• "crownGraph(ZZ)" -- see crownGraph -- Returns a crown graph
• "cycleGraph(ZZ)" -- see cycleGraph -- Constructs a cycle graph
• "degeneracy(Graph)" -- see degeneracy -- Computes the degeneracy of a graph
• degree(Digraph,Thing) -- returns the degree of a vertex in a digraph
• "degreeCentrality(Graph,Thing)" -- see degreeCentrality -- Returns the degreeCentrality of a vertex of a graph
• "degreeIn(Digraph,Thing)" -- see degreeIn -- returns the "in-degree" of a vertex in a digraph
• "degreeMatrix(Digraph)" -- see degreeMatrix -- Returns the degree matrix of a graph
• "degreeOut(Digraph,Thing)" -- see degreeOut -- returns the "out-degree" of a vertex in a digraph
• "deleteEdges(Graph,List)" -- see deleteEdges -- Deletes a list of edges from a graph
• "deleteVertex(Graph,Thing)" -- see deleteVertex -- a method for deleting the vertex of a graph
• "deleteVertices(Digraph,List)" -- see deleteVertices -- Deletes specified vertices from a digraph or graph
• "density(Graph)" -- see density -- computes the density of a graph
• "depthFirstSearch(Digraph)" -- see depthFirstSearch -- runs a depth first search on the digraph or digraph and returns the discovery time and finishing time for each vertex in the digraph
• "descendants(Digraph,Thing)" -- see descendants -- returns the descendants of a digraph
• "diameter(Graph)" -- see diameter -- Computes the diameter of a graph
• "digraph(HashTable)" -- see digraph -- Constructs a digraph
• "digraph(List)" -- see digraph -- Constructs a digraph
• "digraph(List,List)" -- see digraph -- Constructs a digraph
• "digraph(List,Matrix)" -- see digraph -- Constructs a digraph
• "digraph(Matrix)" -- see digraph -- Constructs a digraph
• "digraphTranspose(Digraph)" -- see digraphTranspose -- returns the transpose of a Digraph
• "directProduct(Graph,Graph)" -- see directProduct -- Computes the direct product of two graphs
• "disjointUnion(List)" -- see disjointUnion -- Returns the disjoint union of a list of graphs.
• "displayGraph(Digraph)" -- see displayGraph -- displays a digraph or graph using Graphviz
• "displayGraph(String,Digraph)" -- see displayGraph -- displays a digraph or graph using Graphviz
• "displayGraph(String,String,Digraph)" -- see displayGraph -- displays a digraph or graph using Graphviz
• "distance(Digraph,Thing,Thing)" -- see distance -- Computes the distance between two vertexSet in a graph
• "distanceMatrix(Digraph)" -- see distanceMatrix -- Computes the distance matrix of a digraph
• "doubleStar(ZZ,ZZ)" -- see doubleStar -- returns a double star graph
• "eccentricity(Graph,Thing)" -- see eccentricity -- Returns the eccentricity of a vertex of a graph
• "edgeConnectivity(Graph)" -- see edgeConnectivity -- computes the edge connectivity of a graph
• "edgeCuts(Graph)" -- see edgeCuts -- returns the edge cuts of a graph
• "edgeIdeal(Graph)" -- see edgeIdeal -- returns the edge ideal of a graph
• "edges(Digraph)" -- see edges -- Returns the edges of a digraph or graph
• "edges(Graph)" -- see edges -- Returns the edges of a digraph or graph
• "expansion(Graph)" -- see expansion -- returns the expansion of a graph
• "findPaths(Digraph,Thing,ZZ)" -- see findPaths -- finds all the paths in a digraph of a given length starting at a given vertex
• "floydWarshall(Digraph)" -- see floydWarshall -- runs the Floyd-Warshall algorithm on a digraph to determine the minimum distance from one vertex to another in the digraph
• "forefathers(Digraph,Thing)" -- see forefathers -- returns the forefathers of a digrah
• "friendshipGraph(ZZ)" -- see friendshipGraph -- Returns a friendship Graph
• "generalizedPetersenGraph(ZZ,ZZ)" -- see generalizedPetersenGraph -- Returns a generalized petersen graph
• "girth(Graph)" -- see girth -- A method for computing the girth of a graph
• "graph(HashTable)" -- see graph -- Constructs a simple graph
• "graph(List)" -- see graph -- Constructs a simple graph
• "graph(List,List)" -- see graph -- Constructs a simple graph
• "graph(List,Matrix)" -- see graph -- Constructs a simple graph
• "graph(Matrix)" -- see graph -- Constructs a simple graph
• graph(Digraph) -- Returns the legacy G#graph hash table
• "graphComposition(Graph,Graph)" -- see graphComposition -- A method for composing two graphs
• "graphLibrary(String)" -- see graphLibrary -- constructs a graph of a type specified in the string input
• "graphPower(Graph,ZZ)" -- see graphPower -- constructs a graph raised to a power
• "hasEulerianTrail(Digraph)" -- see hasEulerianTrail -- determines whether a graph or a digraph has an Eulerian trail
• "hasEulerianTrail(Graph)" -- see hasEulerianTrail -- determines whether a graph or a digraph has an Eulerian trail
• "hasOddHole(Graph)" -- see hasOddHole -- checks whether a graph has a odd hole
• "incidenceMatrix(Graph)" -- see incidenceMatrix -- computes the incidence matrix of a graph
• "independenceComplex(Graph)" -- see independenceComplex -- constructs the independence complex of a graph
• "independenceNumber(Graph)" -- see independenceNumber -- computes the independence number of a graph
• "indexLabelGraph(Digraph)" -- see indexLabelGraph -- Relabels the vertices of a graph or digraph according to their indices, indexed from 0.
• "indexLabelGraph(Graph)" -- see indexLabelGraph -- Relabels the vertices of a graph or digraph according to their indices, indexed from 0.
• "inducedSubgraph(Digraph,List)" -- see inducedSubgraph -- A method for finding the induced subgraph of any Graph or Digraph
• "inducedSubgraph(Graph,List)" -- see inducedSubgraph -- A method for finding the induced subgraph of any Graph or Digraph
• "isBipartite(Graph)" -- see isBipartite -- determines whether a graph is bipartite
• "isChordal(Graph)" -- see isChordal -- checks whether a graph is chordal
• "isCM(Graph)" -- see isCM -- determines if a graph is Cohen-Macaulay
• "isConnected(Graph)" -- see isConnected -- determines whether a graph is connected
• "isCyclic(Graph)" -- see isCyclic -- determines whether a graph is cyclic
• isCyclic(Digraph) -- determines whether a digraph is cyclic
• "isEulerian(Digraph)" -- see isEulerian -- determines if a graph or digraph is Eulerian
• "isEulerian(Graph)" -- see isEulerian -- determines if a graph or digraph is Eulerian
• "isForest(Graph)" -- see isForest -- determines whether a graph is a forest
• "isLeaf(Graph,Thing)" -- see isLeaf -- determines whether a vertex is a leaf
• "isPerfect(Graph)" -- see isPerfect -- checks whether a graph is perfect
• "isReachable(Digraph,Thing,Thing)" -- see isReachable -- checks if a vertex u is reachable from a vertex v
• "isRegular(Graph)" -- see isRegular -- determines whether a graph is regular
• "isRigid(Graph)" -- see isRigid -- checks if a graph is rigid
• "isSimple(Graph)" -- see isSimple -- checks if a graph is simple
• "isSink(Digraph,Thing)" -- see isSink -- determines if a vertex of a digraph is a sink or not
• "isSource(Digraph,Thing)" -- see isSource -- determines if a vertex of a digraph is a source or not
• "isStronglyConnected(Digraph)" -- see isStronglyConnected -- checks if a digraph is strongly connected
• "isTree(Graph)" -- see isTree -- determines whether a graph is a tree
• "isWeaklyConnected(Digraph)" -- see isWeaklyConnected -- checks if a digraph is weakly connected
• "kneserGraph(ZZ,ZZ)" -- see kneserGraph -- constructs a kneser graph of specified size
• "laplacianMatrix(Graph)" -- see laplacianMatrix -- Returns the laplacian matrix of a graph
• "leaves(Graph)" -- see leaves -- lists the leaves of a tree graph
• "lineGraph(Graph)" -- see lineGraph -- Returns the line graph of an undirected graph
• "lollipopGraph(ZZ,ZZ)" -- see lollipopGraph -- constructs a lollipop graph
• "lowestCommonAncestors(Digraph,Thing,Thing)" -- see lowestCommonAncestors -- determines the lowest common ancestors between two vertexSet
• "minimalDegree(Graph)" -- see minimalDegree -- computes the minimal degree of a graph
• "minimalVertexCuts(Graph)" -- see minimalVertexCuts -- finds the minimal vertex cuts of a graph
• "monomialGraph(MonomialIdeal,ZZ)" -- see monomialGraph -- Returns a monomial graph
• "neighbors(Graph,Thing)" -- see neighbors -- returns the neighbors of a vertex in a graph
• "nondescendants(Digraph,Thing)" -- see nondescendants -- returns the nondescendants of a vertex of a digraph
• "nonneighbors(Graph,Thing)" -- see nonneighbors -- returns the non-neighbors of a vertex in a graph
• "numberOfComponents(Graph)" -- see numberOfComponents -- computes the number of connected components of a graph
• "numberOfTriangles(Graph)" -- see numberOfTriangles -- counts how many subtriangles are present in a graph
• "parents(Digraph,Thing)" -- see parents -- returns the parents of a vertex on a digraph
• "pathGraph(ZZ)" -- see pathGraph -- A method that makes a path graph
• "rattleGraph(ZZ,ZZ)" -- see rattleGraph -- Returns a rattle graph
• "reachable(Digraph,List)" -- see reachable -- Returns the vertices reachable in a digraph from a given collection of vertices
• "reachable(Digraph,Set)" -- see reachable -- Returns the vertices reachable in a digraph from a given collection of vertices
• "reindexBy(Digraph,String)" -- see reindexBy -- reindexes the vertices according to the input ordering.
• "reindexBy(Graph,String)" -- see reindexBy -- reindexes the vertices according to the input ordering.
• "reverseBreadthFirstSearch(Digraph,Thing)" -- see reverseBreadthFirstSearch -- runs a reverse breadth first search on the digraph and returns a list of the vertexSet in the order they were discovered
• "showTikZ(Digraph)" -- see showTikZ -- Writes a string of TikZ syntax that can be pasted into a .tex file to display G
• "sinks(Digraph)" -- see sinks -- returns the sinks of a digraph
• "sources(Digraph)" -- see sources -- returns the sources of a digraph
• "spanningForest(Graph)" -- see spanningForest -- constructs a spanning forest of a graph
• "spectrum(Graph)" -- see spectrum -- Returns the spectrum of a graph
• "starGraph(ZZ)" -- see starGraph -- Returns a star graph
• "strongProduct(Graph,Graph)" -- see strongProduct -- a method for taking the strong product of two graphs
• "thresholdGraph(List)" -- see thresholdGraph -- A method that generates a threshold graph from a binary list
• "topologicalSort(Digraph)" -- see topologicalSort -- outputs a list of vertices in a topologically sorted order of a DAG.
• "topologicalSort(Digraph,String)" -- see topologicalSort -- outputs a list of vertices in a topologically sorted order of a DAG.
• "topSort(Digraph)" -- see topSort -- outputs a hashtable containing original digraph, new digraph with vertices topologically sorted and a map from vertices of original digraph to new digraph.
• "topSort(Digraph,String)" -- see topSort -- outputs a hashtable containing original digraph, new digraph with vertices topologically sorted and a map from vertices of original digraph to new digraph.
• "underlyingGraph(Digraph)" -- see underlyingGraph -- Returns the underlying graph of a digraph
• "vertexConnectivity(Graph)" -- see vertexConnectivity -- computes the vertex connectivity of a graph
• "vertexCoverNumber(Graph)" -- see vertexCoverNumber -- returns the vertex cover number of a graph
• "vertexCovers(Graph)" -- see vertexCovers -- returns a list of the minimal vertex covers of a graph
• "vertexCuts(Graph)" -- see vertexCuts -- lists all the vertex cuts of a graph
• "vertexMultiplication(Graph,Thing,Thing)" -- see vertexMultiplication
• "vertexSet(Digraph)" -- see vertexSet -- Returns the vertices of a graph or digraph
• "vertices(Digraph)" -- see vertexSet -- Returns the vertices of a graph or digraph
• "wheelGraph(ZZ)" -- see wheelGraph -- Constructs a wheel graph
• "windmillGraph(ZZ,ZZ)" -- see windmillGraph -- Constructs a windmill graph
• "writeDotFile(String,Graph)" -- see writeDotFile -- Writes a graph to a dot file with a specified filename
• Symbols
• discoveryTime (missing documentation)
• EntryMode (missing documentation)
• finishingTime (missing documentation)
• newDigraph -- key used in the output of topSort
• simpleGraph (missing documentation)
• Singletons (missing documentation)

## For the programmer

The object Graphs is .