Definitions:
Note: Many of the following graphs are drawn in Figures
1 and 2.
A graph is null (sometimes, empty) if both its vertex set and edge set are empty.
The bouquet of n loops, denoted Bn, is a graph with one vertex and n self-loops.
The dipole Dn is the graph with two vertices and a multi-edge of
multiplicity n joining them.
The complete graph Kn is a simple graph with n vertices in which every pair of vertices
is adjacent.
The n-path Pn is a graph that “looks like” a path n −
1 edges long. It consists of a sequence
of n vertices V = {v1, v2 . . . , vn} and a
sequence of n−1 edges joining successive vertices
in the sequence, that is, the n − 1
edges are {v1, v2}, {v2, v3}, . . . , {vn−1, vn}.
A path is a graph that is an n-path for some n ≥
0.
The n-cycle Cn is a graph that “looks like” a cycle. It has a
“wraparound” sequence of vertices V = {v1, v2, . . . , vn} and a
sequence of edges joining successive vertices in the sequence, i.e., the n edges are {v1, v2}, {v2, v3}, . . . , {vn−1, vn}, {vn, v1}.
A cycle is a graph which is an n-cycle,for any n
> 0.
The n-wheel is the join of K1 and
the n-cycle.
A graph is bipartite
if its vertices can be partitioned
into two subsets (the parts, or partite sets) so that no two vertices in the same part are adjacent.
The complete bipartite
graph Kr,s is the simple bipartite graph in which the two parts
have respective cardinalities r and s, such that every vertex in one part is adjacent to
every vertex in the other part.
The complete r-partite
graph
has r disjoint subsets of vertices of orders n1, n2, . . . , nr, with two vertices adjacent if and only if they lie
in different subsets. If the r sets all have t vertices,this graph is
sometimes denoted Kr(t).
The d-dimensional
hypercube graph Qd is a graph with 2d vertices that can be labeled
with the 2d bitstrings of length d so that two vertices are adjacent if
and only if their labels differ in exactly one bit.
A graph G is connected if for each pair of vertices in G, there is a
path in G that contains them both.
A tree is a connected graph without any cycles as subgraphs.
A forest is a graph without any cycles as subgraphs.
The Kuratowski
graphs are the graphs K5 and K3,3.
The intersection graph for a
collection F = {Sj} of subsets of the same set has as its nodes the subsets themselves.
There is an edge between each pair of subsets whose intersection is not empty.
An interval graph is any graph
isomorphic to the intersection graph for a collection of intervals of the real
line.
Facts:
1. In a computer program, the null graph is used as the initial value of a
graph-valued variable, rather like the way that an integer-valued variable is
initialized to zero. As the program runs, the graph-valued variable can be
modified by adding vertices and edges.
2. Bouquets and dipoles are fundamental building blocks for graphs
constructed by topological techniques.
3. The path graph Pn is a tree.
4. A graph is bipartite if and only if it has no cycles of odd length.
5. Trees are bipartite.
6. The hypercube graphs Qn can be defined recursively as follows: Q0 = K1,
Qn = K2 × Qn−1 for n
> 0.
7. The hypercube graph Qn is bipartite and is isomorphic to the lattice of subsets of a set of n elements.