MMiDS 5.4: Self-Assessment Quiz

Which of the following is NOT a property of the Laplacian matrix \( L \) of a graph \( G \)?

• a) \( L \) is symmetric.
• b) \( L \) is positive semidefinite.
• c) The constant unit vector \(\frac{1}{\sqrt{n}}(1,\ldots,1)^T\) is an eigenvector of \( L \) with eigenvalue 0.
• d) \( L \) is positive definite.

What is the algebraic connectivity of a graph?

• a) The largest eigenvalue of the Laplacian matrix.
• b) The smallest eigenvalue of the Laplacian matrix.
• c) The second smallest eigenvalue of the Laplacian matrix.
• d) The average of all eigenvalues of the Laplacian matrix.

Which vector is known as the Fiedler vector?

• a) The eigenvector corresponding to the largest eigenvalue of the Laplacian matrix.
• b) The eigenvector corresponding to the smallest eigenvalue of the Laplacian matrix.
• c) The eigenvector corresponding to the second smallest eigenvalue of the Laplacian matrix.
• d) The eigenvector corresponding to the average of all eigenvalues of the Laplacian matrix.

For a connected graph \( G \), which of the following statements about the second smallest eigenvalue \( \mu_2 \) of its Laplacian matrix is true?

• a) \( \mu_2 = 0 \)
• b) \( \mu_2 < 0 \)
• c) \( \mu_2 > 0 \)
• d) The value of \( \mu_2 \) cannot be determined without additional information.

Consider a graph \( G \) with two connected components. What is the value of the second smallest eigenvalue \( \mu_2 \) of its Laplacian matrix?

• a) \( -1 \)
• b) \( 0 \)
• c) \( 1 \)
• d) \( 2 \)

If a graph has \( k \) connected components, what is the multiplicity of 0 as an eigenvalue of its Laplacian matrix?

• a) 0
• b) 1
• c) \( k-1 \)
• d) \( k \)

The Laplacian quadratic form \( x^T L x \) for a graph \( G \) with Laplacian matrix \( L \) can be written as:

\[ x^T L x = \sum_{\{i,j\} \in E} (x_i - x_j)^2. \]

What does this quadratic form measure?

• a) The average distance between vertices in the graph.
• b) The number of connected components in the graph.
• c) The "smoothness" of the function \( x \) over the graph.
• d) The degree of each vertex in the graph.

The Laplacian matrix \( L \) of a graph \( G \) can be decomposed as \( L = B B^T \), where \( B \) is the oriented incidence matrix. What does this decomposition imply about \( L \)?

• a) \( L \) is positive definite
• b) \( L \) is symmetric and positive semidefinite
• c) \( L \) is antisymmetric
• d) \( L \) is a diagonal matrix