20240312: Graphs cont.

Question 1

(Disjoint) Union

Definition; notation

Answer 1

• Union of two simple graphs G and H: G∪H = ((V(G)∪V(H)), (E(G)∪E(H)))
• Disjoint union of two graphs with no common vertices: the number of connected components; disjoint union denoted by: G+H, connected components denoted by: c(G)

Question 2

Cartesian product

Definition; notation; characteristics

Answer 2

Cartesian product of two simple graphs G and H: G□H
- vertex set: V(G)×V(H)
- edge set: all pairs (u_1, v_1)(u_2, v_2), such that: u_1u_2 is in E(G) and v_1 = v_2 or v_1v_2 is in E(H) and u_1 = u_2

Question 3

Digraph

Definition

Answer 3

A directed graph D is an ordered pair (V, A) consisting of a set of vertices and a set of directed edges (arcs), disjoint from V, together with an incidence function Ψ that associates with each arc an ordered pair of not necessarily distinct vertices in V.

Question 4

Neighbourhood

Notation

Digraph

Answer 4

• number of arcs: a(D)
• in-neighbourhood: N-(v); all arcs pointing to v
• out-neighbourhood: N+(v); all arcs pointing from v

Question 5

True or false:

Digraph D has an underlying graph G with the edge set corresponding to the arcs in D.

Answer 5

True.
Denoted by G(D)

Question 6

Orientation and tournament

Definition

Answer 6

An orientation of a graph G is a digraph D whose arc set corresponds to the edge set of G.
A tournament is an orientation of a complete graph.

Question 7

True or false:

An indegree of a vertex v: the number of the arcs going away from v.
An outdegree of a vertex v: the number of the arcs coming into v.

Digraph

Answer 7

False.
It’s the other way around. Indegree shows how many arcs are coming into a vertex, and outdegree shows how many arcs are going away from v.

Question 8

In and outdegree; minimum and maximum in and outdegree

Notation

Digraph

Answer 8

• indegree of v: d-(v)
• outdegree of v: d+(v)
• min. indegree of D: δ-(D); min. outdegree of D: δ+(D)
• max. indegree of D: Δ-(D); max. outdegree of D: Δ+(D)

Question 9

True or false:

A directed path(cycle) is a path(cycle) with an orientation in which each vertex dominates its successor in the sequence.

Answer 9

True.

Question 10

Edge deletion; vertex deletion

Terminology; notation

Answer 10

• edge deletion: obtaining a graph with m-1 edges by deleting an edge e, but leaving the incident vertices and adjacent edges intact; denoted by G\e
• vertex deletion: obtaining a graph with n-1 vertices by deleting a vertex v, and all of its incident edges; denoted by G-v

Question 11

Subgraph

Definition; characteristics

Answer 11

• a subgraph F of G: V(F), E(F) are subsets of V(G), E(G)
• incidence function Ψ is a restriction on E(F)
• it can be obtained by repeated edge and vertex deletion
• null graph is a subgraph of all graphs
• and every graph is a subgraph and a supergraph of itself

Question 12

True or false:

A maximal path is the longest path in the graph.

Explain

Answer 12

False.
- a maximum path is the longest one in the graph (can be extended in a way it doesn’t violate the constraints of a path)
- a maximal path is a path that cannot be extended from either end.

Question 13

Circumference; girth

Terminology

Answer 13

• circumference: the length of the longest cycle in G
• girth: the length of the shortest cycle in G

Question 14

True or false:

A spanning subgraph is obtained by edge and vertex deletion.

Answer 14

False.
A spanning subgraph: V(SS) = V(G), E(SS) is a subset of E(G) -> a spanning subgraph is obtained only by edge deletions.

Question 15

Hamilton path and cycle

Terminology

Answer 15

• Hamilton path: spanning path
• Hamilton cycle: spanning cycle

Question 16

Induced subgraph

Definition; notation

Answer 16

• obtained by vertex deletions; denoted by: G[Y]
• a subgraph of G induced by Y: V(G[Y]) = Y; E(G[Y]): all edges with both ends in Y

Question 17

Operations: Identifying; contracting; subdividing

Terminology; notation

Answer 17

• identifying some vertices x and y is to replace them with a single vertex incident to all edges incident to x or y; denoted by: G{x, y}
• contracting an edge e is to delete an edge and then identify its ends (if there are any); denoted by: G/e
• subdividing an edge e is to delete e, add a new vertex x and join x to ends of e

Question 18

Graph decomposition

Definition; terminology

Answer 18

• a family F of edge-disjoint subgraphs of G, such that union of edge sets of those subgraphs yields E(G)
• path decomposition: decomposition of G consisting only of paths
• cycle decomposition: decomposition of G consisting only of cycles

Question 19

Edge cut

Definition; notation

Answer 19

• denoted by: E[X, Y] is a set of edges in G with one end in X and the other in Y
• e(X, Y) denotes the number of such edges
• Edge cut is the smallest such number of edges needed to remove to disconnect the graph.