Definitions

Question 1

What is the distance, dist_G(u,v), between two vertices u and v in graph G?

Answer 1

The length of the shortest uv-path

Question 2

What is the eccentricity, ecc(v) of a vertex v in a graph G?

Answer 2

The maximum distance between v and any vertex of G:= max{dist(u,v): u in V(G)}

Question 3

What is the diameterof G, diam(G)?

Answer 3

The maximum eccentricity in G:= max{ecc(v): v in V(G)}

Question 4

What is the radius of G, rad(G)?

Answer 4

The minimum eccentricity in G:= min{ecc(v): v in V(G)}

Question 5

If G is disconnected then what is the eccentricity of any vertex?

Answer 5

Infinity

Question 6

What is the centre, C(G), of a connected graph G?

Answer 6

The subgraph induced by the set of vertices in G with minimum eccentricity

Question 7

What is a breadth first spanning tree?

Answer 7

If T is a spanning tree of a connected graph G, then for every pair of vertices v, r, dist_T(v,r) = dist_G(v,r)

Question 8

In a weighted graph what is the length of a path?

Answer 8

The sum of the weights on the edges on the path.

Question 9

What is the shortest path in a weighted graph?

Answer 9

dist(u,v)

Question 10

What is a bipartition of a graph G?

Answer 10

If the vertex set can be partitioned into two subsets A and B such that every edge connects a vertex from one set to a vertex in the other and no edges connect vertices in the same set. Then {A,B} is the bipartition of G.

Question 11

In Menger’s theorem what is an AB-path in the graph G?

Answer 11

For sets A,B in V(G) and AB-path has one endpoint in A and the other endpoint in B.

Question 12

In Menger’s theorem what is an AB-separator?

Answer 12

The set S in V(G) is an AB-separator if every AB-path includes a vertex in S.

Question 13

In Menger’s theorem what is s(G,A,B)?

Answer 13

The minimum number of vertices in an AB-separator. It is also the upper limit for the number of pairwise disjoint AB-paths.

Question 14

What is a cut vertex, v, in graph G?

Answer 14

v is a cut vertex if G-v has more components than G

Question 15

What is a vertex cutset in graph G?

Answer 15

A set X in V(G) such that G-X is disconnected.

Question 16

What does it mean for a graph G to be k-connected?

Answer 16

G must have more than k vertices and every cutset has size at least k.

Question 17

What is the connectivity, kappa(G), of a graph G?

Answer 17

The maximum k such that G is k-connected. Alternatively it is the smallest set of vertices that leave G disconnected.

Question 18

What is an edge cutset of graph G?

Answer 18

A subset U of E(G) such that G-U is disconnected.

Question 19

What does it mean for a graph G to be edge k-connected?

Answer 19

|V(G)| >= 2 and every edge cutset has size at least k.

Question 20

What is the edge-connectivity of a graph G, lamba(G)?

Answer 20

The maximum k such that G is edge k-connected. Alternatively it is the minimum size of an edge cutset.

Question 21

When are two paths in a graph G edge-disjoint?

Answer 21

If they have no edges in common

Question 22

In Menger’s theorem what is t(G,x,y)?

Answer 22

The minimum number of edges whose deletion destroys all xy-paths in G.

Question 23

What is a digraph?

Answer 23

A graph with edges given direction

Question 24

What is the set A(G) in a digraph G?

Answer 24

The set of ordered pairs of vertices called arcs consisting of a tail, u, and a head, v, denoted by (u,v) or simply uv.