[VE]ij= 
The vertex-edge incidence matrix of a graph G, denoted VE, is an unsymmetrical (and, in general, not a square) V × E matrix, which is determined by the incidences of vertices and edges in G [2,12-16]:
[VE]ij= |
1 if the i-th vertex is incident with the j-th edge |
| 0 otherwise (37) |
As an example we give in Figure 24 the vertex-edge incidence matrix of a branched tree T2.
T2
Figure 24. Vertex-labeled and edge-labeled branched tree T2 representing the carbon skeleton of 2,3-dimethylhexane.
a |
b |
c |
d |
e |
f |
g |
||||
VE(T2)= |
1 |  |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
 |
| 2 | 1 |
1 |
0 |
0 |
0 |
1 |
0 |
|||
| 3 | 0 |
1 |
1 |
0 |
0 |
0 |
1 |
|||
| 4 | 0 |
0 |
1 |
1 |
0 |
0 |
0 |
|||
| 5 | 0 |
0 |
0 |
1 |
1 |
0 |
0 |
|||
| 6 | 0 |
0 |
0 |
0 |
1 |
0 |
0 |
|||
| 7 | 0 |
0 |
0 |
0 |
0 |
0 |
1 |
|||
| 8 | 0 |
0 |
0 |
0 |
0 |
1 |
0 |
The above definition (37) may be further extended to oriented graphs, graphs in which all edges have an assigned direction. If a graph G is oriented, then the non-zero elements of the vertex-edge incidence matrix of G are +1 or -1 depending on the direction of the edges [13]. The +1 values indicate positively incident edges, whilst the -1 values negatively incident edges [176]. An example of an oriented polycyclic graph is given in Figure 25.
Figure 25. Oriented tricyclic graph.
The vertex-edge incident matrix associated with G 14 is given below.
a |
b |
c |
d |
e |
f |
g |
h |
i |
j |
k |
l |
m |
||||
VE(G14)= |
1 | |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
|
| 2 | -1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|||
| 3 | 0 |
-1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|||
| 4 | 0 |
0 |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|||
| 5 | 0 |
0 |
0 |
1 |
1 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
|||
| 6 | 0 |
0 |
0 |
0 |
-1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|||
| 7 | 0 |
0 |
0 |
0 |
0 |
-1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|||
| 8 | 0 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
-1 |
0 |
0 |
0 |
0 |
|||
| 9 | 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
0 |
0 |
0 |
|||
| 10 | 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
1 |
0 |
|||
| 11 | 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
A more general description of the vertex-edge incidence matrix can be given [177]. A vertex-edge incidence matrix VE with rows and columns labeled by members of two sets I (with the members denoted by i) and J (with the members denoted by j) of subgraphs of a graph G can be defined as:
[VE]ij=  |
1 if sets I and J have a non-zero intersection |
| 0 otherwise (38) |
If I is the set of vertices and J the set of edges, (38) reduces to (37).
The vertex-edge incidence matrix found some use in chemistry, e.g., as long ago as 1940 Balandin employed this matrix, called the property matrix, in his study of the molecular physical and chemical properties [101], though this work seems to have been largely overlooked [102]. More recently a few information-theoretic indices have been based on this matrix [21,178-180].
