Search

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.

For a graph G = (V , E) , an edge connectivity λ is the minimum number of edges whose removal disconnects G. In this paper, we define property restricted edge connectivity. Then we appraise its particular case, more precisely k-restricted edge connectivity. Some of the basic properties of k-restricted edge connectivity are considered. We also discuss how k-restricted edge connectivity associates with graph coloring. In particular, we try to study how k-restricted edge connectivity relates with Tait's coloring theorem and thereby the famous Four-color conjecture. [ABSTRACT FROM AUTHOR]