1 Could the matrix below be the distance matrix of some graph? Explain. 0 1 2 2

Question

1 Could the matrix below be the distance matrix of some graph? Explain. 0 1 2 2 3 1 0 1 4 2 2 1 0 2 1 3 2 1 3 0 2. For G given below, 02 U1 U3 Us 07 Ug U10 U12 011 (a) find the radius and diameter of G (b) find the center and periphery of G (c) identify, if possible, any mutually eccentric vertices in G 3. A geodesic joining a vertex in the center of a graph to one of its eccentric vertices is called a radial path. Identify a radial path in G from question 2, A pair of vertices u,u E V(G) such that d(u,u)= diamG) is called diametral. A geodesic joining two diametral vertices is called a diametral path. Identify a diametral path in G from question 2. 4· 5. 6. Explain why the center of Cn is V(C). A graph with this property is called self-centered. (Really!) Let H be a spanning subgraph of graph G. Given verticesu and U in G, show that dH(u,u) dG (u,e). Suppose rad(G) = 4, what are the possible values of diam(G)? Find two more classes of self-centered graphs.

Explanation / Answer

1) The given matrix could be a distance matrix for some graph.

Since the elements along diagonal of the matrix represent the distance of vertices from themselves only which is zero and hence justified in the given matrix. This is a 5 * 5 matrix which represent 5 vertex graph.

The given matrix is symmetric hence the matrix is equal to the transpose of the given matrix which is again a condition for distance matrix.

For instance the element a12 in the given graph is equal to 1 .After taking transpose the matrix the element a12 becomes a21 which is also equal to 1 and they represent the same distance between two points back and forth.

Hence the given matrix could be a disatnce matrix.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.