There's a number of graph utilities and tricks I use when working with graphs in Mathematica 8, I've summarized them in notebook graphUsage.nb. You can get this notebook and all required packages here.
programmatically changing style of existing graph, modifying graphs without forgetting vertex coordinates, using GraphPlot's layout for Graph objects, aligning adjacency matrix with vertex labels in index graphs
Listing graph structures
cliques, independent sets, maximal cliques, maximal independent sets, hamiltonian circuits
Showing all graphs that miss particular properties, visualizing graphs with intensity attached to vertices -- pieGraph and fadedGraph. Showing graph with several types of vertices.