Counting Components via Spectra of Adjacency Matrices

Question

I trying to implement a test for $k$-connectedness of cubic triangle-free graphs $G$ given their adjacency matrix $A$. My idea is the following:

For $1$-connectedness, we construct a new graph $G'$ by the following process:

1. Remove the first $\color{red}{\text{edge}}$ (you choose any)
2. and the two resulting $\color{red}{\text{vertices of degree $2$ }}$
3. and reconnect the left-over vertices:

$\hskip2in$

[Since triangles are forbidden, the graph will stay simple.]

This can be done for the adjacency matrix as well by

1. setting the offdiagonal entry that represents the $\color{red}{\text{red edge}}$ to $0$,
2. removing the dimensions that represent the $\color{red}{\text{red vertices}}$
3. and setting the offdiagonal entry that represents the $\color{black}{\text{black edges}}$ to $1$.

By that, we get $A'$ of $G'$ and will then calculate the eigenvalues of $A'$. We do this for all edges. If the graph was initially $1$-connected and we, at a certain point, remove the $\color{red}{\text{bridge }}$, we are left with two components and the spectrum of $A'$ will have two eigenvalues of $3$.

If there is no bridge, we continue with removing pairs of edges, calculate the spectra and watch out for multiple eigenvalues to check for $2$-connectedness and so forth.

Is there any reason why this shouldn't work? How would this algorithm compare to the ones given at Wikipedia?

... More generally, it is easy to determine computationally whether a graph is connected (for example, by using a disjoint-set data structure), or to count the number of connected components...

Seem like I invented counting components via spectra of adjacency matrices?

Answer 1

Few thoughts/comments.

1. The graph may not remain simple in the second iteration since the first iteration my produce triangles.

2. In order to evaluate your algorithm, you'd have to explain how to fix the above problem.

3. It is well known that the number of connected components of a $r$-regular graph is in fact the multiplicity of the eigenvalue $r$.

4. If the graph is in fact bipartite, then it is automatically $2$-connected.

5. It is always possible to reduce a cubic graph of order $n+2$ to a cubic graph of order $n$ by using a so called $H$ reduction with is essentialy what you're doing here but handles the thing with triangles. See this paper for example.