Discussion
Which of the properties hold for the adjacency matrix \(A\) of a simple undirected unweighted graph having \(n\) vertices?
Answer: A
The property that holds is The diagonal entries of \(A^{2}\) are the degrees of the vertices of the graph.
\((A^{2})_{ii} = \sum_{j} a_{ij} a_{ji} = \sum_{j} a_{ij}^{2} = \sum_{j} a_{ij}\), since \(A\) is symmetric with entries 0 or 1. That sum counts the neighbours of vertex \(i\), which is its degree.
The others fail. For the path on three vertices u - v - w (\(n = 3\)), the graph is connected, but \(A^{2} + I_{3}\) has a 0 in position (u, v): there is no walk of length exactly 2 from u to v, because the graph is bipartite. A triangle plus one isolated vertex has \(n = 4\) and its entries sum to \(6 = 2(n-1)\), yet it has a cycle. Two disjoint edges on four vertices put a 1 in every row and column, but the graph is not connected.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development