Skip to main content
Wanted to make it clearer that this is a reference request.
Link

Reference request: Strong Connectivity and the Incidence Matrix

added 309 characters in body; edited title
Source Link

Strong ConnectednessConnectivity and Incidence Matrix

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 matrixincidence 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!

Strong Connectedness and Incidence Matrix

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.

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!

Strong Connectivity and Incidence Matrix

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!

Source Link

Strong Connectedness and Incidence Matrix

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.

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!