FiniteGraphs produces a convenient list of all the interesting, finite, parameterless graphs built into Combinatorica.
FruchtGraph returns the smallest 3-regular graph whose automorphism group consists of only the identity.
GraphComplement[g] gives the complement of graph g.
GraphProduct[g_1, g_2, ...] constructs the product of graphs g_1, g_2, and so forth.
GraphSum[g_1, g_2, ...] constructs the graph resulting from joining the edge lists of graphs g_1, g_2, and so forth.
GrayCodeKSubsets[l, k] generates k-subsets of l in Gray code order.
HamiltonianPath[g] finds a Hamiltonian path in graph g if one exists. HamiltonianPath[g, All] gives all Hamiltonian paths of graph g.
HasseDiagram[g] constructs a Hasse diagram of the relation defined by directed acyclic graph g.
HeapSort[l] performs a heap sort on the items of list l.
IntervalGraph[l] constructs the interval graph defined by the list of intervals l.