Exams › GATE › Technical

Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?

1. The diagonal entries of A² are the degrees of the vertices of the graph.
2. If the graph is connected, then none of the entries of A^(n−1) + Iₙ can be zero.
3. If the sum of all the elements of A is at most 2(n−1), then the graph must be acyclic.
4. If there is at least a 1 in each of A's rows and columns, then the graph must be connected.

Correct answer: The diagonal entries of A² are the degrees of the vertices of the graph.

Solution

The diagonal entries of A² represent the sum of the products of corresponding entries in the rows and columns of the adjacency matrix, which counts the number of edges connected to each vertex, thus giving the degree of each vertex.

Related GATE Technical questions

• Which one of the following regular expressions correctly represents the language of the finite automaton given below?
• Which one of the following statements is TRUE?
• In a relational data model, which one of the following statements is TRUE?
• Consider the problem of reversing a singly linked list. To take an example, given the linked list below, head -> a -> b -> c -> d -> e -> NULL, the reversed linked list should look like head -> e -> d -> c -> b -> a -> NULL. Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?
• Suppose we are given n keys, m hash table slots, and two simple uniform hash functions h1 and h2. Further suppose our hashing scheme uses h1 for the odd keys and h2 for the even keys. What is the expected number of keys in a slot?
• Which one of the following facilitates transfer of bulk data from hard disk to main memory with the highest throughput?

⚔️ Practice GATE Technical free + battle 1v1 →