[eA]ij= 
The edge-adjacency matrix, denoted by eA, of an edge-labeled connected graph G is a square E × E matrix which is determined by the adjacencies of edges [2,15]:
[eA]ij= |
1 if edges i and j are adjacent |
| 0 otherwise (8) |
Below we give the edge-adjacency matrix of the edge-labeled graph G1 (see structure B in Figure 2).
eA(G1)= |
 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|||
0 |
1 |
0 |
1 |
0 |
0 |
1 |
|||
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|||
0 |
0 |
0 |
1 |
0 |
1 |
1 |
|||
0 |
0 |
0 |
0 |
1 |
0 |
1 |
|||
0 |
1 |
1 |
0 |
1 |
1 |
0 |
It should be noted that the vertex-adjacency matrix uniquely determines a graph, but the edge-adjacency matrix does not, that is, there are known graphs with identical edge-adjacency matrices. A pair of nonisomorphic graphs - the three-point star S3 and the cycle on three vertices C3 - possessing identical edge-adjacency matrices is given in figure 10.
Figure 10. A pair of nonisomorfic graphs consisting of the 3-star S3 and the 3-cycle C3 that possess the same edge-adjacency matrix.
Below we give the edge-adjacency matrix that represents both S3 and C3.
eA(S3)= eA(C3)= |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|||
1 |
1 |
0 |
S3 and C3 clearly possess different vertex-adjacency matrices - they are graphs of different sizes - and they have a different number of vertices.
It should also be noted that the edge-adjacency matrix of graph G is identical to the vertex-adjacency matrix of the corresponding line graph L(G) of G:
eA(G) = eA(L(G)) (9)
This must be so because the edges in G are replaced by vertices in L(G) [12]. In Figure 11, we show the construction of the line graph L(G1) from graph G1.
Figure 11. Construction of the line graph L(G1) from the graph G1.
It is interesting to note that the line graph concept, though not in the explicit mathematical formalism, may be traced back to the beginnings of structural chemistry. Thus, van't Hoff represented simple organic molecules in terms of points and lines, that is, in terms of the line graphs of the modern structural formulas [e.g., 108].
A number of topological indices mentioned above can be reformulated in terms of the edge-degrees instead of the vertex-degrees, e.g., the total edge-adjacency index [21], the reformulated Zagreb indices [109,110], the edge-connectivity index [111,112,372], the reformulated Gordon-Scantebury index [21], and the reformulated Platt index [21].
