Question: What would be a good reference for characterizations of strong connectivity of a digraph in terms of its incidence matrix?

Details: Consider a digraph $(V, E)$ with vertex set

$$V = \{v_1, \ldots, v_m\}$$

and edge set

$$E = \{e_1, \ldots, e_n\} = \{(v_{11},v_{12}), \ldots, (v_{n1},v_{n2})\} \subseteq V \times V\,.$$

The incidence matrix $M$ of $(V, E)$ is the $|V| \times |E|$ matrix defined by,

$$M_{ij} = -1, \quad \text{if} \ v_{1j} = v_i\,,$$ $$M_{ij} = 1, \quad \text{if} \ v_{2j} = v_i\,,$$ $$M_{ij} = 0, \quad \text{otherwise}\,.$$

Thus, an entry $M_{ij}$ is $-1$ if edge $j$ leaves vertex $i$, $1$ if edge $j$ reaches vertex $i$, and $0$ otherwise.

The digraph $(V, E)$ is said to be strongly connected if, for any two vertices $v, v' \in V$, there exists a directed path connecting $v$ and $v'$; in other words, there exist vertices $v^{(1)}, \ldots, v^{(k)} \in V$ such that

$$(v, v_1), (v_1, v_2), \ldots, (v_{k-1}, v_k), (v_k, v') \in E\,.$$

Context: I am familiar with characterizations of strong connectivity in terms of the adjacency matrix, but not the incidence matrix. A Google search has not yielded anything helpful in that direction.

Thanks in advance!

  • $\begingroup$ In your details you should probably add what you mean by strong connectivity. $\endgroup$
    – Todd Trimble
    Aug 14 '15 at 14:29
  • $\begingroup$ Good point; done! Thanks for the suggestion. $\endgroup$ Aug 14 '15 at 14:33

It needs to be the case that for every $(0,1)$-vector $x$ (other than the zero vector and the all-ones vector) the vector $M^Tx$ has at least one entry positive and one entry negative.

Otherwise, if this fails for some vector $x$, then you have that $X=\{i\in V : x_i\neq 0\}$ is a set of vertices such that all arcs incident to one vertex in $X$ and one not in $X$ go "in the same direction" -- i.e., either all such arcs leave $X$ or they all enter $X$, and of course the existence of such a (nonempty, proper) set of vertices is what it means for strong connectivity to fail. (Well, unless such an $x$ actually makes $M^Tx$ zero, in which case the graph isn't even weakly connected.)


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.