# Graphs

## Authors

• Jack Burkart
• David Cook II
• Caroline Jansen
• Amelia Taylor
• Augustine O'Keefe
• Contributers of note: Alex Diaz, Luis Garcia, Shaowei Lin, Sonja Mapes, Mike Stillman, Doug Torrance

## Version

This documentation describes version 0.3.2 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
• 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)
• bigraph (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
• collateVertices (missing documentation)
• 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
• labeledGraph (missing documentation)
• 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
• mixedGraph (missing documentation)
• 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 (missing documentation)
• topSort (missing documentation)
• 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
• barycenter(Graph), see barycenter -- Returns the barycenter of a grah
• bigraph(MixedGraph) (missing documentation)
• 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
• children(MixedGraph,Thing) (missing documentation)
• 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
• clusteringCoefficient(Graph) (missing documentation)
• clusteringCoefficient(Graph,Thing) (missing documentation)
• collateVertices(MixedGraph) (missing documentation)
• complementGraph(Graph), see complementGraph -- Returns the complement of a 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
• degeneracy(Graph), see degeneracy -- Computes the degeneracy of a graph
• degree(Digraph,Thing) -- returns the degree of a vertex in a digraph
• degree(Graph,Thing) (missing documentation)
• 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
• deleteEdges(Digraph,List) (missing documentation)
• deleteVertex(Graph,Thing), see deleteVertex -- a method for deleting the vertex of a graph
• deleteVertex(Digraph,Thing) (missing documentation)
• 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
• descendants(MixedGraph,Thing) (missing documentation)
• diameter(Graph), see diameter -- Computes the diameter of a graph
• Digraph _ List (missing documentation)
• Digraph _ ZZ (missing documentation)
• Digraph _* (missing documentation)
• digraph(MixedGraph) (missing documentation)
• digraphTranspose(Digraph), see digraphTranspose -- returns the transpose of a Digraph
• directProduct(Graph,Graph), see directProduct -- Computes the direct product of two 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
• distance(Digraph,Thing) (missing documentation)
• distanceMatrix(Digraph), see distanceMatrix -- Computes the distance matrix of a digraph
• 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
• forefathers(MixedGraph,Thing) (missing documentation)
• girth(Graph), see girth -- A method for computing the girth of a graph
• graph(Digraph) -- Returns the legacy G#graph hash table
• graph(LabeledGraph) (missing documentation)
• graph(MixedGraph) (missing documentation)
• graphComposition(Graph,Graph), see graphComposition -- A method for composing two graphs
• 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
• labeledGraph(Digraph,List) (missing documentation)
• 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
• 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
• mixedGraph(Digraph) (missing documentation)
• mixedGraph(Digraph,Bigraph) (missing documentation)
• mixedGraph(Graph,Digraph) (missing documentation)
• mixedGraph(Graph,Digraph,Bigraph) (missing documentation)
• neighbors(Graph,Thing), see neighbors -- returns the neighbors of a vertex in a graph
• neighbors(MixedGraph,Thing) (missing documentation)
• net(Digraph) (missing documentation)
• net(LabeledGraph) (missing documentation)
• net(MixedGraph) (missing documentation)
• nondescendants(Digraph,Thing), see nondescendants -- returns the nondescendants of a vertex of a digraph
• nondescendants(MixedGraph,Thing) (missing documentation)
• nonneighbors(Graph,Thing), see nonneighbors -- returns the non-neighbors of a vertex in a graph
• nonneighbors(MixedGraph,Thing) (missing documentation)
• 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
• parents(MixedGraph,Thing) (missing documentation)
• 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
• strongProduct(Graph,Graph), see strongProduct -- a method for taking the strong product of two graphs
• topologicalSort(Digraph) (missing documentation)
• topologicalSort(Digraph,String) (missing documentation)
• topSort(Digraph) (missing documentation)
• toString(Digraph) (missing documentation)
• toString(LabeledGraph) (missing documentation)
• toString(MixedGraph) (missing documentation)
• 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
• vertices(MixedGraph) (missing documentation)
• 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 (missing documentation)
• simpleGraph (missing documentation)
• Singletons (missing documentation)