An adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not. In the special case of a finite simple graph, the adjacency matrix is a (0,1)-matrix with zeros on its diagonal.

219 questions
Filter by
Sorted by
Tagged with
22 views

### Smallest spectral radius of signed Petersen graph

I have come across a question that requires finding the smallest spectral radius of a signed Petersen graph, i.e., find the smallest $p \geq 0$ such that there exists a signed adjacency matrix of the ...
• 1
32 views

1 vote
150 views

### Examples of graph problems that are $\Omega(n^2)$ when using adjacency matrix representation.

I recently learned about this very nice way to prove that given a simple undirected graph $G = (V, E)$, given as an adjacency matrix $A$, any algorithm deciding if $G$ is Hamiltonian is $\Omega(n^2)$. ...
• 583
134 views

### Let G be a graph with connected components, give adjacency matrix.

Let G be a graph with connected components $G_1,\: \ldots ,\: G_l$, and $V(G_1)=\{u_1^1,\: u_2^1,\: \ldots ,\: u_{n_1}^1\},\: V(G_l)=\{u_1^l,\: u_2^l,\: \ldots ,\: u_{n_l}^l\}$ their set of vertices, ...
• 282
131 views

### Checking if two digraphs are isomorphic from their adjacency matrices

Wikipedia says that, given digraphs $G_1$ and $G_2$ whose adjacency matrices are $A_1$ and $A_2$ respectively, $G_1$ and $G_2$ are isomorphic if and only if there exists a permutation ...
• 188
520 views

### Largest eigenvalue of a simple graph

Let $\Gamma$ be a simple graph with $n$ vertices, $e$ edges and largest eigenvalue $\lambda_{max}$. Show that $\lambda_{max} = \frac{2e}{n}$ iff $\Gamma$ is regular. I've already shown the if part, ...
• 297
1 vote
79 views

### Prove if $\operatorname{adj}(A) = O$ then $\operatorname{rank}A \leq n-2$

Prove if $\operatorname{adj}(A) =0$, then $\operatorname{rank}A \leq n-2$ My initial idea is to setup an induction. Base case $A \in M_{2×2}$ which obviously implies that \$A = [O]_{2×2} \rightarrow \...
• 1,625