Anti-Adjacency Matrices of Certain Graphs Derived from Some Graph Operations

Abstract

If we go through the literature, one can find many matrices that are derived for a given simple graph. The one among them is the anti-adjacency matrix which is given as follows; The anti-adjacency matrix of a simple undirected graph $G$ with vertex set $V (G) \,= \,\{\,v_1,\,v_2,\\ \dots, v_n\}$ is an $n \times n$ matrix $B(G) = (b_{ij} )$, where $b_{ij} = 0$ if there exists an edge between $v_i$ and $v_j$ and $1$ otherwise. In this paper, we try to bring out an expression, which establishes a connection between the anti-adjacency matrices of the two graphs $G_1$ and $G_2$ and the anti-adjacency matrix of their tensor product, $G_1 \otimes G_2$. In addition, an expression for the anti-adjacency matrix of the disjunction of two graphs, $G_1\lor G_2$, is obtained in a similar way. Finally, we obtain an expression for the anti-adjacency matrix for the generalized tensor product and generalized disjunction of two graphs. Adjacency and anti-adjacency matrices are square matrices that are used to represent a finite graph in graph theory and computer science. The matrix elements show whether a pair of vertices in the graph are adjacent or not.

Keywords

• anti-adjacency matrix, tensor product, disjunction, generalized tensor product and generalized disjunction.