Tuesday, 20 August 2013

Counting Components via Spectra of Adjacency Matrices

Counting Components via Spectra of Adjacency Matrices

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:
Remove the first $\color{red}{\text{edge}}$ (you choose any)
and the two resulting $\color{red}{\text{vertices of degree $2$ }}$
and reconnect the left-over vertices:

[Since triangles are forbidden, the graph will stay simple.]
This can be done for the adjacency matrix as well by
setting the offdiagonal entry that represents the $\color{red}{\text{red
edge}}$ to $0$,
removing the dimensions that represent the $\color{red}{\text{red vertices}}$
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?

No comments:

Post a Comment