Definitions Flashcards
Neighbour set
For any vertex v in V(G), the neighbour set of v, by N(v), is the set of all vertices, except for v itself, that are adjacent to v.
Simple graphs
A graph is called a simple graph if it does not contain multiple
edges between the same pair of vertices nor loops (i.e., edges from and to
the same vertex).
Degree of vertex
the number of edges of
G incident to v, and it is denoted by δ(v). Here, loops are counted twice
Handshaking lemma
In any graph G, we have:
∑v∈V (G) δ(v) = 2|E(G)|.
aka: the sum of vertices’s degrees in V(G) is equal to two times the size of E(G)
(Here, |E(G)| is the size of E(G).)
Degree sequence
a list of the degrees of the
vertices of G. The sequence is ordered if the numbers are in non-decreasing
order.
Graphic degree sequence
A sequence of numbers is called graphic if it is the degree sequence of a simple graph.
Subgraph
Given a graph G, a graph H is a subgraph of G if V (H) ⊆V (G) and E(H) ⊆E(G).
Subgraph induced by vertex subset
Given a graph G and a subset of its vertices, V ∗ ⊆V (G), the
subgraph induced by V ∗ has vertex set V ∗ and edge set
{〈u,v〉∈E(G) | u,v ∈V ∗}. The subgraph induced by V ∗ is denoted by
G[V ∗].
Subgraph induced by edge subset
Given a graph G and a subset of its edges, E∗ ⊆E(G), the
subgraph induced by E∗ has edge set E∗ and vertex set
{u,v ∈V (G) | 〈u,v〉∈E∗}. The subgraph induced by V ∗ is denoted by
G[E∗].
Graph isomorphism
Graphs G1 and G2 are called isomorphic if there is a one-to-one
mapping φ : V (G1) →V (G2) such that:- For each edge 〈u,v〉∈E(G1), there’s an edge 〈φ(u),φ(v)〉∈E(G2) and
vice versa. (We call φ(u) and φ(v) the corresponding vertices of u and v in
G2.)
Walk
a walk is a sequence of vertices and edges such that ei = [vi-1,vi] is an edge in G, for all i = 1,2,…,k
Path
a path is a walk but over distinct vertices
Cycle
is a path of at least 3 edges
Connectivity
two vertices are connected if there exists a path. additionally, a graph is connected if all pairs of vertices are connected
Component
a connected subgraph which is not strictly contained in another connected subgraph
Vertex cut
removing the vertices V* and their edges will make the graph disconnected
Edge cut
removing edges E* from the graph makes it disconnected
Kappa
minimum number of vertices to remove to disconnected G
Lambda
minimum number of edges we need to remove to disconnect the graph
Simple Complete Graph
n > 2 vertices denoted by Kn, if the degree of each vertex is exactly n-1
