Computer Sciences > Gate 2022 > Graph representation

Contributed by: Dr. Sarah Chen

Report Correct Copyright Claim

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

A

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

B

If the graph is connected, then none of the entries of A^n-1+I_n can be zero.

C

If the sum of all the elements of A is at most 2(n-1), then the graph must be acyclic.

D

If there is at least a 1 in each of A’s rows and columns, then the graph must be connected.

Check Answer

Explanation

Correct : a

Similar Questions

What is the worst-case time complexity of insertion in an AVL tree?

Question #23 Medium

Which operations on a binary search tree have O(h) complexity?

Question #31 Easy

Compare search complexities of sorted array vs balanced BST.

Question #47 Hard

Related Topics

Data Structures Binary Search Tree Time Complexity Algorithm Analysis Tree Algorithms Computer Science