Graph G
V(G), E(G), Psi(G)
Parallel edges
ones that are incident with the same vertices
adjacent vertices (v ~ u)
some edge exists where psi(G) = uv
neighbor of v is u
u ? v, u ~ v (N_G(v) is set of neighbors)
null graph
V(G) = E(G) = ?
loopless graph
no loops
simple graph
no loops or parallel edges
underlying standard simple graph
delete loops, reduce parallel edges to single endge
complement Gbar of G
V(Gbar) = V(G), E(Gbar) = (V(G) C 2) - E(G)
Incidence matrix MG
index rows by vertices, columns by edges
number in matrix is how many times edge is incident with vertex (2 for loops)
adjacency matrix Ag
index both rows and columns by vertices. loops count as 2 in the diagonal
degree(v)
number of ends of edges incident with v
k-regular
all degrees are k
maximum degree
?(G)
minimum degree
?(G)
avg degree
d(G)
degree sequence of G
list of all degrees in no order
degree sum formula
sum of all degrees = 2m
what does avg degree of graph equal
2m/n
d_Gbar(v)
n - 1 - d_G(v)
identical graphs G, H
V(G) = V(H). E(G) = E(H). psi(G) = psi(H)
isomorphism from G to H
pair (?, y) where ? is a bijection from V(G) to V(H) and psi is a bijection from E(G) to E(H).
For standard simple graphs, give ?.
For finite graphs, if we know the edge sets are the same size and ?,y are bijections, it's enough to check one direction of
labelled graph
graph
unlabelled graph
equivalence class of graphs
invariant
property that is same for all isomorphic graphs
automorphism of G
G is an isomorphism to itself. Associative.
Aut G is a group by composition
Asymmetric graph
only automorphic with one's self
Similar vertices u, v
automorphism mapping u to v
coboundary ?_G(X)
set of edges of G with one end in X and the other not.
disconnected
if you can partition G into two nonempty sets X,Y such that there are no edges from X to Y, then it is disconnected.
or
If there is any set X that is not null nor the whole graph and it has no coboundary, the graph is disconnected.
connected
not disconnected
planar graph
can be drawn in plane without edge crossings
embeddable in S
can be drawn in S without edge crossings
cycle C_n
connected n-vertex 2 regular graph
path P_n
C_n with an edge deleted
Independent/stable set S of G
no loops on S and vertices of S are pairwise nonadjacent
independence number of G
max number of vertices in a stable set in G
clique S of G
any two vertices in S are adjacent in G
clique number of G
max size of clique in G
complete graph K_n
simple n-vertex, any two distinct vertices are adjacent
trivial graph
K_1
supercomplete graph
not necessarily simple, but definitely complete
empty or edgless graph
K_n^bar. n vertices, no edges
bipartite graph
can partition V(G) into two sets X,Y (could be empty) so that every edge has one end in X and the other end in Y. G = G[X,Y]
complete bipartite graph K_m,n
simple G[X,Y] where every x in X is adjacent to every y in Y
k-partite graph
can partition V(G) into K sets so that each set is independent
complete k-partite graph
k-partite simple graph where any two vertices are adjacent unless in the same independent set
subgraph F
V(F) in V(G). E(F) in E(G). psi(F) bounded by psi(G).
proper subgraph
subgraph but not equal
disjoint subgraphs
no common vertices
edge-disjoint subgraphs
no common edges
spanning subgraph F
V(F) = V(G)
hamilton path/cycle
hamilton path/cycle
k-factor
spanning k-regular subgraph
component
maximal connected subgraph
induced subgraph G[S]
vertex set is S, all edges of G with both ends in S
edge-induced subgraph G[T]
edge set is T, vertex set is all ends of all edges in T
line graph L(G) of simple graph
V(L(G)) = E(G), make e and f adjacent in L(G) if they are incident with a common vertex in G
union intersection of graphs G, H
can be defined if they are consistent, which means their incident functions agree with one another.
take the union/intersection and inherit incidence from G, H, or both
cartesian product, GboxH
one copy of G for every node in H
one copy of H for every node in G
lexicographical product of G and H
like cartesian product except the adjacencies are maintained thru the copies
m x n grid
P_m x P_n
Join G v H of disjoint G,H
join every vertex of G to every vertex of H
if simple, bar(G v H) = bar(G) U bar(H)
walk in G
alternating sequence of vertices and edges W = v1, e1, v2, e2...eL-1, vL where psi(e_i) = v(i-1), v(i)
reverse walk
W^-1
closed walk
initial vertex = final vertex
trail
walk with no repeated edges
path
walk with no repeated vertices
cycle
closed walk with no repeated vertices besides initial/last
reachability relation R_G
u R_G v means there is a uv-walk in G. Also an equivalence relation
distance
length of shortest path
euler trail
trail using all edges and vertices of G
euler tour
closed euler trail
acyclic graph or forest
no cycles
tree
nonnull connected forest
leaf
degree 1 vertex
cutedge e
G - e has more components than G
cutvertex v
G - v has more components than G
rooted tree, r-tree
tree with special designated vertex r. there is a unique rv path rTv
ancestor of v
any vertex of rTv (including v)
parent p(v)
immediate predecessor on rTv (root has none)
proper ancestor
ancestor but not itself
level of v l(v)
d_T(r, v)
Global TCM
keep picking edges that don't form a cycle til u can't
Local TCM
Global TCM but starting from a root r where u can only add to the component containing R
BFS
local TCM where new vertices are added as early as possible