As we know, the Fiedler vector is the eigenvector corresponding to the second smallest eigenvalue and this vector can be used for graph partitioning. We also know that this vector comes from a relaxed quadratic optimization problem to find the Min-Cut in a balanced way. I have two questions in this regard.
Is there any constraints on the eigenvalues (eigengap) for the Fiedler vector to be meaningful? For example, is Fiedler vector meaningful if the second smallest eigen value is close to zero?
Since the Fiedler vector is the solution of the relaxed optimization problem, is there any well-known approximation ratio for it, or can we analyze how far the solution is from the optimal one?
Thank you in advance