The Vertex-Adjacency Matrix of Simple Graphs

The vertex-adjacency matrix or binary matrix, denoted by A, of a vertex-labeled connected simple graph G with Vvertices is a square VxVmatrix, which is determined by the adjacencies of vertices in G (Harary, 1971)  

FIGURE 2.1 A vertex-labeled (A) and edge-labeled (B) graph G.  

It is evident that is a symmetric matrix with a zero diagonal. Therefore, the transpose A of the vertex-adjacency matrix leaves A unchanged  

If the vertex-adjacency matrix is associated with the graph G composed of two components and G,  

FIGURE 2.2 Graph with conveniently labeled vertices to give the vertex-adjacency matrix in the block-diagonal form. 

---