As of Version 10, most of the functionality of the Combinatorica package is built into the Wolfram System. >>

Constructing Graphs

 

ReferenceReference

MakeGraph construct a graph using a binary predicate

FunctionalGraph construct a graph with edges defined by functional relations

IntervalGraph construct a graph defined by the list of intervals

LineGraph  ▪  NonLineGraphs  ▪  Path

SmallestCyclicGroupGraph  ▪  ResidualFlowGraph

Graph Modifications

AddEdge, AddEdges add edges to a graph

DeleteEdge, DeleteEdges remove edges from a graph

RemoveSelfLoops delete self-loops in a graph

RemoveMultipleEdges delete multiple edges

MakeSimple simplify the graph

MakeDirected  ▪  MakeUndirected  ▪  NormalizeVertices

AddVertex  ▪  AddVertices  ▪  DeleteVertex  ▪  DeleteVertices

ChangeVertices  ▪  ChangeEdges  ▪  ReverseEdges  ▪  DeleteCycle

Contract merge vertices into one

InduceSubgraph make graph with a subset of edges and vertices

PermuteSubgraph permute selected vertices

VertexCover vertex cover of the graph

MaximumClique  ▪  MinimumVertexCover  ▪  VertexCoverQ

GreedyVertexCover  ▪  ApproximateVertexCover  ▪  MaximalMatching

IndependentSetQ  ▪  MaximumIndependentSet

RegularGraph create a regular graph

RegularQ  ▪  DegreeSequence  ▪  RealizeDegreeSequence

GraphUnion merge graphs together

GraphIntersection find a common subgraph

TransitiveClosure find the transitive closure of a graph

GraphComplement  ▪  GraphDifference

GraphSum  ▪  GraphJoin  ▪  GraphProduct  ▪  CartesianProduct

Random Graphs

RandomGraph generate a random graph

NthPair get a pair of vertices from enumeration

DegreeSequence list number of edges for each vertex

ExactRandomGraph  ▪  GraphicQ  ▪  RealizeDegreeSequence  ▪  RandomVertices

Trees

RandomTree generate a random tree

LabeledTreeToCode convert tree to Prüfer code

CompleteBinaryTree tree with two branches for each node

CodeToLabeledTree  ▪  CompleteKaryTree  ▪  TreeIsomorphismQ

TreeToCertificate  ▪  TreeQ