Question

How can the adjacency matrix of \(\bar G\)be found from the adjacency matrix of G, where G is a simple graph?

Short answer

By switching all 1’s of matrix into 0’s and 0’s into 1’s can G be made an adjacent matrix.

Step-by-step solution

Concept/Significance of adjacency matrix

An adjacency matrix represents the cost of moving from node a to node b. The probability of travelling from node a to node b is represented by the transitions matrix.

Determine adjacency matrix of \(\bar G\) is found from the adjacency matrix of G

Let A be the adjacent matrix of\(G\)with respect to the order of\({v_1},\;{v_2},........,{v_n},\)the vertex set of G.

When\({\left( {i,\;j} \right)^{th}},\)term of A is adjacent to 1 and when it is 0, the set is not adjacent.

Then, the complementary graph's edges are exactly defined to be next to the regular graph's opposite vertices, and all 1’s are changed to 0’s and all 0’s arechanged to 1’s in the adjacency matrix form.

Thus, by switching all 1’s of matrix into 0’s of the matrix \(G\) and 0’s into 1’s of the matrix \(G\) can the adjacent matrix\(\bar G\)be obtained fromthe adjacent matrix\(G.\)