2
$\begingroup$

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$enter image description here

[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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1 thanks. Concerning 1. and 2.: If a triangle pops up, I would replace it by a single cubic vertex... $\endgroup$ – draks ... Aug 20 '13 at 20:35
  • $\begingroup$ @draks... how would your code verify if the graph is $3$-connected? $\endgroup$ – Jernej Aug 20 '13 at 20:40
  • $\begingroup$ Looks like a bit of book keeping, but in fact just iterating through all sets of three edges that show up during the process of removing edges. There might be some cases where my algorithm will check certain combinations more than once, I guess... $\endgroup$ – draks ... Aug 20 '13 at 20:45
  • 1
    $\begingroup$ @draks... The thing is that this already appears to be less efficient than the straightforward "consider all 3-subsets of vertices, remove them, check if the graph stays connected" algorithm... $\endgroup$ – Jernej Aug 20 '13 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.