Here we present two ways of constructing graphical matrices, denoted by G, that lead to four types of these matrices. One way is to define the elements of the graphical matrix [G]ij as the subgraphs obtained after the consecutive removal of edges connecting vertices i and j from the graph G. We denote this kind of graphical matrices by eG, where e stands for the edge and we call them edge-graphical matrices. The matrix eG is necessarily a sparse matrix, since it contains only a few non-vanishing elements corresponding to the removed edges. An example of this kind of graphical matrix is given in Figure 43. Since the graphical matrix is a square symmetric V × V matrix, it is enough for demonstrative purposes to give only the upper triangle of the matrix. For graphs without loops, the corresponding graphical matrices have zeros as diagonal elements.
Figure 43. The edge-graphical matrix of T2 from Figure 24.
However, if we generate the graphical matrix by the consecutive removal of paths joining vertices i and j instead of edges, the obtained matrix is dense. We call this matrix the path-graphical matrix and denote it by pG. An illustrative example of a path-graphical matrix is given in Figure 44.
Figure 44. The path-graphical matrix of T2 from Figure 24.
A second way to construct graphical matrices is to define their elements [G]ij as the subgraphs obtained after the consecutive removal of adjacent vertices i and j, and the incident edges from the graph G. The graphical matrices so obtained are by necessity sparse matrices, since they contain only a few non-vanishing elements corresponding to the deleted adjacent vertices and incident edges. We denote this kind of graphical matrix by svG, where s denotes the sparse matrix and v stands for the adjacent vertices, and we call these matrices the sparse vertex-graphical matrices. An example of such a matrix is given in Figure 45.
Figure 45. The sparse vertex-graphical matrix T2 from Figure 24.
If, instead of considering only adjacent vertices, we consider pairs of vertices i and j at increasing distances, the graphical matrix obtained is dense, that is, all its matrix-elements except the diagonal elements are non-zero. We denote this matrix by dvG, where d denotes the dense matrix, and call it the dense vertex-graphical matrix. In Figure 46, we give the dense vertex-graphical matrix of T2.
Figure 46. The dense vertex-graphical matrix of T2 from Figure 24.
