91Ó°ÊÓ

How many cycles does a connected graph of order \(n\) with \(n\) edges have?

Apply the BF-algorithm of Section \(11.7\) to determine a BFS-tree for the following: (a) The graph of the regular dodecahedron (any root) (b) GraphBuster (any root) (c) A graph of order \(n\) whose edges are arranged in a cycle (any root) (d) A complete graph \(K_{n}\) (any root) (e) A complete bipartite graph \(K_{m, n}\) (a left-vertex root, and a right- vertex root) In each case, determine the breadth-first numbers and the distance of each vertex from the root chosen.

Let \(G\) be a graph with \(n\) vertices \(x_{1}, x_{2}, \ldots, x_{n} .\) Let \(r_{i}\) be the largest of the distances of \(x_{i}\) to the other vertices of \(G\). Then $$ d(G)=\max \left\\{r_{1}, r_{2}, \ldots, r_{n}\right\\} \text { and } r(G)=\min \left\\{r_{1}, r_{2}, \ldots, r_{n}\right\\} $$ are called. respectively, the diameter and radius of \(G\). The center of \(G\) is the subgraph of \(G\) induced by the set of those vertices \(x_{i}\) for which \(r_{i}=r(G)\), Prove the following assertions: (a) Determine the radius, diameter, and center of the complete bipartite graph \(K_{m, n}\) (b) Determine the radius, diameter, and center of a cycle graph \(C_{n} .\) (c) Determine the radius, diameter, and center of a path with \(n\) vertices. (d) Determine the radius, diameter, and center of the graph \(Q_{n}\) corresponding to the vertices and edges of an \(n\) -dimensional cube.