Home > Flashcards > Print Preview
The flashcards below were created by user
Jamie_Bee
on FreezingBlue Flashcards. What would you like to do?

Neighbourhood
The neighbourhood of a vertex v is the set of neighbours of v, and is denoted by N_{G}(v)

Underlying simple graph of G
The simple graph obtained by deleting all loops and all but one of each set of multiple edges


Clique
a set of pairwise adjacent vertices.

clique number and symbol
 cardinality of a largest clique in G
 ω(G)

independent/stable set
set of pariwise nonadjacent vertices

independence number and symbol
 cardinality of a largest independent set in G
 α(G)

chromatic number and symbol
 the minimum number of colours needed to colour the vertices of G so that distinct adjacent vertices receive different colours
 χ(G)

kpartite graph
the vertex set of a kpartite graph can be partitioned into k independent sets

planar
A graph is planar if it is possible to draw a diagram of it in the plane without crossing.

path
a simple graph whose vertices are ordered so that two vertices are adjacent if and only if they're consecutive

cycle
a graph whose vertices are ordered in a circle so that two vertices are adjacent if and only if they are consecutive on the circle.

subgraph
a subgraph of G is a graph H such that V(H)⊆V(G) and E(H)⊆E(G), and the assignment of endpoints to edges in H is the same as in G

degree of a vertex v in a graph G
the number of edges incident with v, with each loop counting as two edges.

minimum degree symbol
δ(G)

maximum degree symbol
Δ(G)

incidence matrix and symbol
 M(G)
 nxm matrix with rows as the vertex set and columns the edge set, in which the ij0th entri is the number of times v_{i} is incident with e_{j}

adjacency matrix of G and symbol
 A(G)
 nxn matrix with rows and columns indexed by the vertex set of G, in which the ijth entry is the number of edges joining v_{i} and v_{j} in G

Two graphs G and H are identical (equal) if
V(G)=V(H), E(G)=E(H)

Isomorphism
A simple graph G is said to be isomorphic to a simple graph H if there is a bijection f:V(G)→V(H) such that uv∈E(G)⇔ f(u)f(v)∈E(H)

Line graph
the simple graph with vertex set V(L(G))=E(G) in which two vertices are joined if and only if they are adjacent edges in G.

self complementary graphs
A simple graph G is self complementary if G≃

a decomposition of a graph G
 a list of subgraphs of G such that each edge of G lies in exactly one subgraph in the list.
 The edge sets of the subgraphs in the list partition the edges set of G.

kregular
a graph is kregular if d_{G}(V) = k for all v∈V(G)

girth
 length of a shortest cycle measured in number of edges
 If G has no cycles we say G has infinite girth

Union of Graphs G_{1}, G_{2}, ..., G_{k}
the graph with vertex set and the edge set

Disjoint union or sum
If the graphs G_{1,}G_{2,}G_{k }have pairwisedisjoint vertex sets, then the disjoint union or sum is denoted by G_{1}+G_{2}+...+G_{k}

HFree
A graph G is Hfree if G has no induced subgraph isomorphic to H.

walk of length k
an ordered list of alternating vertices and edges

trail
a walk with no repeated edge

path
a walk with no repeated vertex (and no repeated edge)

length of a walk, trail, path or cycle
number of edges, including repetitions if any

concatenation in a graph G
 Given a (u,v)path P and a (v,w)path Q in G, the concatenation PQ is the (uw,)walk obtained by following P from u to v, then following Q from v to w.
 P^{1} denotes the (v,u)path obtained by traversing P backwards from v to u.

cutedge (cutvertex)
a edge e (vertex v) such that Ge (Gv) ihas more components than G

Eulerian trail
a trail which uses every edge of G exactly once

When is a graph Eulerian?
 If it contains a Eulerian circuit, which is a closed Eulerian trail
 Result: A graph G is Eulerian if and only if it has at most one nontrivial component and is even.

even (odd) graph
a graph in which all vertices have even (odd) degree.

maximal path in a graph G
a path which is not contained in a longer path of G

maximum path in G
a path of maximum length.

order and symbol
 n(G)
 Order is the cardinality of the vertex set of G

size and symbol
 e(G)
 Size is the cardinality of the edge set of G

degree sequence
is the list of vertex degrees of a graph, usually written in nonincreasing order.

graphic
a degree sequence of nonnegative integers is graphic if there is a simple graph with degree sequence d.

acyclic
graph with no cycles


tree
connected acyclic graph

leaf or pendant vertex
vertex with degree 1

spanning tree of graph G
 spanning subgraph H of G that is a tree
 ie, V(G)=V(G)

distance from u to v
 if vertices u and v are connected in graph G, then the distance from u to v denoted by d_{G}(u,v) is the length of a shortest (u,v)path in G.
 If u and v are not connected in G, then d_{G}(u,v) = ∞

diameter and symbol
 diam(G)
 maximum distance between any two vertices of G
 Not the length of the longest path but the length of the longest shortest path

eccentricity of a vertex u in a graph G and symbol

radius of a graph G and symbol
 rad(G)

center of a graph G
 Subgraph of G induced by the vertices of minimum eccentricity
 ie, the vertices of u such that

contracted and symbol
 An edge e of a graph G is said to be contracted if it is deleted and its endpoints are identified.
 G•e

optimal tree
minimumweight spanning tree

greedy algorithms
locally optimal heuristics (practical method)

