Prove that vector 1 (vector with all entries as 1) is an eigenvector of the adjacency matrix corresponding to eigenvalue k if and only if the graph is a k-regular graph.
What will be an ideal response?
Proof. For a
k-regular graph, the adjacency matxix contains exacly
k number of 1’s, and as a result sum of each row is
k. Therefore,
A1=k1.
Hence,1 is an eigenvector corresponding to the eigenvalue k. Now we need to prove the reverse statement. Let us assume that
1 is the eigenvector corresponding to the eigenvalue k. We have to prove that it is possible for only k-regular graphs.
Based on the assumption, we have
A1=k1
Therefore, the sum of each row of the adjacency matrix is
k. This is possible only for k-regular graphs.
You might also like to view...
Display all student names and birth dates. Display birth dates with the format ‘20 OCTOBER, 1970’.
Write queries for the following. (Use tables created in Chapter 4 Lab Activity.)
When a video editor needs to bring in a video file from a VHS tape, which of the following would most likely be needed?
A) Surround sound card B) Geotracking C) Sound controller D) Video capture card
When will the TextChanged event occur for a combo box? Which style allows the user to edit the text of the combo box?
What will be an ideal response?
Item D in the accompanying figure is used to preview the content of an interactive form.
Answer the following statement true (T) or false (F)