2
$\begingroup$

Do incidence matrices fully characterize a graph? In other words, is it sufficient to retain the incidence matrix of a graph in order to know everything about it, namely, its connectivity (edge set), vertex set and underlying topology? As opposed to e.g. the degree matrix, which does not contain complete information on how the nodes are wired or directed in case of a digraph.

$\endgroup$
1
  • $\begingroup$ Yes, each non-zero entry corresponds to a (vertex, edge) pair in the graph so the graph is fully characterized. I am not sure exactly what you mean by the "underlying topology," though. $\endgroup$
    – Math1000
    Oct 23, 2019 at 14:17

1 Answer 1

2
$\begingroup$

If you are talking about a simple, undirected graph, then the answer is "yes." From the incidence matrix we can easily construct the adjacency matrix, which clearly fully determines the graph. If graph is directed, the incidence matrix also determines it, since the signs give the orientation of the edges. This works even if there are parallel edges.

If the graph has loops, then the incidence matrix does not determine it. We can tell that an edge is a loop, since the corresponding column is all $0$'s, but we can tell which vertex it is incident on. It would be easy to fix this, by just making the relevant entry $1$ instead of $0$ say, but this is not the usual way of defining the incidence matrix, so far as I am aware.

$\endgroup$
1
  • $\begingroup$ Thank you, exactly what I was trying to learn! $\endgroup$
    – user929304
    Oct 23, 2019 at 15:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .