Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MATH 3330 — Applied Graph Theory

Assignment 4

1. [2] Show that the k-core of a tree is empty for all k ≥ 2. See notes about degree cores, week 5.(MATH3330)

2. (a) [2]Show that for every non-trivial connected graph G,

rad(G) ≤ diam(G) ≤ 2rad(G),

where rad(G) and diam(G) denote the radius and diameter of G, respectively.

(b) [2] Give an example of a graph G where rad(G) = diam(G), and an example of a graph where diam(G) = 2rad(G).

3. [2] Draw a simple graph with 9 vertices, 2 components, 10 edges and exactly two cycles, or give an argument why such a graph does not exist.

4. Consider the graph G below. Read the notes about degree cores, week 5.

(a) [2] For each vertex v of G find the maximum k so that v is in the k-core. This value is sometimes called the core number of v. (Note: you need to find all non-empty degree cores in order to answer this question.)

(b) [1] Explain why the core number of a vertex can never be larger than its degree, but the degree can be larger than the core number. (Use at most 3 sentences.)

5. Consider the graph G below.

(a) [2] Use the adjacency matrix to find the number of walks of length 4 from vertex 0 to vertex 3. I recommend using NetworkX for matrix multiplication; use the worksheet on graphs and matrices in the folder NetworkX on Brightspace for an example.

(b) [1] List all the paths of length 4 from vertex 0 to vertex 3.

6. [2] Draw all spanning trees of the following graph:

Indicate the isomorphism classes among these spanning trees.

7. [4] Describe the BFS tree and a DFS tree for the following graphs: (a) Cn (n odd), (b) Kn. Indicate the root in each tree.