2
$\begingroup$

I am somewhat stuck working on an issue and would really love some guidance. I will state the problem, my current state and what led to it in case the solution lies beyond where I was looking

  • The problem:
    Given an undirected, weighted (with possibly negative weights) graph, I wish to apply injective maps on that graph (they need not be homomorphisms, actually they don't even have to be injective but for my case injective is enough) and I am stuck on the question "Which transformations preserve connected components" in the sense that if exists a path between $u$ and $v$ then exists a path between $f(u)$ and $f(v)$
    Note that this is a weaker condition than homomorphism because I don't care how long the paths are, only that the map preserves the fact that a path exists or does not exist between two vertices.
    In an ideal world, I would even like to be able to describe these transformations as linear transformations acting on the adjacency matrix of the graph.

  • Few things that I have noted so far are:

    1. It is a well known fact the an adjacency matrix is permutation equivalent to a diagonal block matrix where the blocks represent the connected components.
    2. This means that any map which preserves orthogonality of rows (columns) will not decrease the number of connected components but in the event that some of the weights are negative, it may increase it.
      This is what is causing my problem
    3. I feel that the solution I am looking for is the solution to the question "Is there a condition on $T:R^n \to R^n$ s.t. $\forall u,v\in R^n <Tv,Tu>=0 \iff \sum |u_i||v_i|=0 $?"

Any help or guidance towards a source I could read would be much appreciated.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.