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.

208 questions
Filter by
Sorted by
Tagged with
1 vote
14 views

### Find crossing edges in a graph from adjacency matrix

Is there any way to find the crossing edges from the adjacency matrix of a given undirected graph $G=(V,E)$? For example in the following graph ( actually a tree in this specific example) $e_{3, 13}$ ...
27 views

### Powers of adjacent matrix and the path length

I'm really struggling with a question in linear algebra that is associated with graph theory but I honestly have no idea how I should go about it. Graph $G=(E,K)$ consists of a finite set of vertices ...
1 vote
11 views

### Check if adjacency tensor of hypergraph is irreducible

Consider an m-uniform, n-dimensional hypergraph. It's adjacency tensor is an $\overbrace{(n \times n \times ... \times n)}^{m}$ -dimensional tensor $T$. As shown in , to calculate the $(H)$-...
14 views

### Applications of second largest eigenvalue in absolute value

I'm reading a paper where someone attempts to find the second largest eigenvalue in absolute value of the adjacency matrix of a distance-regular graph. That made me wonder: what is this specific ...
288 views

54 views

### Relationship between square of adjacency matrix and Laplacian matrix

Consider a simple undirected graph with $n$ elements. Let $A$ be the adjacency matrix of the graph with elements $a_{ij}$. Let $L$ be the graph Laplacian with $L=D-A$ where $D$ is the degree matrix. ...
1 vote
83 views

1 vote
40 views

### Normalize an adjacency matrix twice

I am working on a graph clustering problem and i've seen that applying two consecutive normalizations on the adjacency matrix gives much better performance than when applying a single one. I first ...
64 views

1 vote
61 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)$. ...
77 views

### Range of eigenvalue in a normalized adjacency matrix

Assuming that $G$ is a simple and undirected graph, no isolated node and let $A$ be the adjacency matrix of $G$. My question is that, what is the range for the eigenvalue of the following normalized ...
66 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, ...
71 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 ...
211 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, ...
1 vote
59 views

1 vote
156 views

### If $A$ is the adjacency matrix of a graph $G$, and $A^3$ has a $1$ on the diagonal, then $G$ has a triangle

If we have a graph $G$, and $A$ the adjacency matrix that represents $G$, how can we proof the diagonal of $A^3$ having a $1$ implies that there is a triangle in $G$? I try to use the theorem that $A$... 1 vote
24 views

### Graph neighbourhood matrix in which each pair of rows has at least one common column full of ones

I am trying to understand a particular method of moments estimation algorithm. If you are interested in that, see this for more detailed description. Long story short, I am trying to understand what ...
1 vote
147 views

### trace of positive integer power of adjacency matrix

I have been trying to calculate cycles cycles in undirected graphs and I have read this article which has really helped but I'm still seeking a shorter way to calculate matrix power traces(it is ...
328 views

### Having number of walks between two vertices how to calculate paths

I know that we can calculate number of walks with n length between two vertices of an undirected graph by calculating the nth power of the adjancy matrix but what if you want to avoid repetition in ...
64 views

### Why do diagonal entries of odd potencies of adjacency matrices of forests sum up to zero?

I came across the statement that the trace (sum of diagonal entries) of an odd potency of an adjacency matrix of a forest is always zero. I have tried out a few options and it seems to be correct for ...
164 views

### How is a matrix connected to a grid?

I have a hard time finding information about and understanding how a matrix (adjacency matrix) is connected to a grid used in numerical analysis. What would the nodes be and are the matrix weighted or ...
1 vote
1k views

### What is the transitive closure of the following digraph?

What is the transitive closure of the following digraph ? To find reach-ability matrix and adjacency matrix. My approach: The adjacency matrix is \begin{bmatrix} 0 &1 &0 &0 \\ 0 & 0&...
1 vote
### Spectrum of a labelled complete graph $K_n$
Suppose, $K_n$ is a complete simple graph with each edge label $k$. Then its adjacency matrix $A(K_n)$ has all the entries zero along the diagonal, and each non-diagonal entries are $k$. What are ...