Any graph is completely determined by either its adjacencies or its incidences. This can be restarted as: Graph adjacencies lead to the adjacency matrices and graph incidences to the incidence matrices, respectively. While the (vertex-)adjacency matrix and its properties have been studied rather thoroughly [e.g.,17,19], the (vertex-edge) incidence matrix has been studied less [15],
although it seems the vertex-edge and edge-cycle incidence matrices were introduced earlier.
For example, at the turn of the century, Poincaré emphasized these matrices when he presented [20] essentially equivalent tableaux appearing in an approach for the construction of geometrical objects (called complexes following Listing [174] ) from elementary units, called cells. In order to describe how the cells fit together, Poincaré used the Kirchhoff technique [164], replacing a system of linear equations by a matrix which he built from his considerations of 0-cells and 1-cells. In present-day terminology the 0-cells and 1-cells are called vertices and edges, which together form a graph. The corresponding matrix is now known as the vertex-edge incidence matrix. Notably, on the strength of this and related papers Poincaré is regarded a founder of algebraic topology [175].
1.
The Vertex-Edge Incidence Matrix
2. The Edge-Vertex Incidence Matrix
3. The Edge-Cycle Incidence Matrix
4. The Cycle-Edge Incidence Matrix
5. The Vertex-Path Incidence Matrix
6. The Weighted-Hexagon-Kekulé-Structure Incidence Matrix