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.

239 questions
Filter by
Sorted by
Tagged with
1 vote
66 views

### I’m trying to find all of the cycles of a directed graph. Is there a more efficient way to do this?

Here’s the graph: My current strategy is to make an adjacency matrix, then follow it, like if A can go to B, then I go to B’s row and see which points B can go to, all the way until I reach the ...
• 11
1 vote
49 views

• 47
16 views

### Do Adjacency and Laplacian cospectral graphs always have the same degree sequence?

I know that the spectrum of the adjacency matrix enumerates the number of closed walks, and the spectrum of the reduced laplacian enumerates the number of spanning trees. Does being both adjacency and ...
47 views

### Show that $(1-\varepsilon(n, d)) \sqrt{d}$ is a lower bound of $\lambda=\max _{i \neq 1}\left|\lambda_i\right|$

Problem: Let $G$ be a $d$-regular graph with adjacency matrix $A$ and eigenvalues $\lambda_1 \geq$ $\lambda_2 \geq \cdots \geq \lambda_n$. Let $\lambda=\max _{i \neq 1}\left|\lambda_i\right|$ be the ...
• 1,302
33 views

### Looking at all permutations of a product of matrices

Let $M$ be an $n \times n$ nonnegative row-stochastic matrix, and let $M_i$ be the matrix whose $i$-th row is the same as that of $M$, and whose remaining rows are all the same as that of the identity ...
1 vote
48 views

### Approaching Graph theory problem with linear algebra

Let $G$ be a undirected graph such that every two vertices have an odd number of common neighbors. Then the graph $G$ has a Euler circle. It is straightforward to see that $G$ is connected as every ...
• 4,653
1 vote
37 views

### From adjacency Matrix can we find the maximum number of disjoint matching pairs of a simple undirected graph?

I came across this problem which boiled down to finding the maximum number of pairs of disjoint edges given a simple undirected graph. After doing some research I came across Edmond's Blossom ...
73 views

• 159
1 vote
61 views

### Trace of power of matrix (arising from number of closed walks)

Let $G_n$ be the graph obtained from the $n-$cube graph $C_n$ by adding one extra edge between each vertex and its antipode (vertex whose label has all $0$'s and $1$'s switched) Note: The $C_n$ graph ...
• 326
65 views

### Existence of a subset S of the set of vertices of a graph given number of walks between any two vertices of some length $l$ are odd

As the title says, Let G be a simple graph with at least 2 vertices. Suppose for some $l\geq 1$ the number of walks of length $l$ between any two vertices of the graph (not necessarily distinct!) is ...
• 326
46 views

• 553
220 views

### Using the matrix of adjacency to find number of paths (not walks)

I am well aware that if $A$ is the adjacency matrix of a graph, then $A^n=a^{(n)}_{ij}$ counts the number of walks of length $n$ from vertex $i$ to vertex $j$. Is there a way to modify this so that ...
1 vote
96 views

### How to calculate all cycles in a directed graph?

I am competing in the American Computer Science League (ACSL), and I get problems similar to the following. Look at this directed graph. Now tell me the number of cycles in said graph. These ...
159 views

### Graph homomorphism with adjacency matrices

Generally with any definition in graph theory, there is a corresponding definition for the adjacency matrix variation of graphs. For example, a graph isomorphism is a mapping between graphs $A$ and $B$...
• 207
123 views

### Finding the optimal adjacency matrix [closed]

Notation: Let $\mathbf{A} \in \{0,1\}^{n \times n}$ be the adjacency matrix of an undirected graph. Let $\mathbf{D}$ be the degree matrix of this graph and let $\mathbf{L} = \mathbf{D} - \mathbf{A}$ ...
• 41
94 views

• 23
1 vote
1k views

### Meaning of eigenvalues of an adjacency matrix

I know the eigen vector of a matrix transformation is the vector that turns it into a scalar transformation. But in the context of a adjacency matrix and in a graph, what does the eigen vector or ...
1 vote
783 views

### Formula for counting the number of subgraphs in a given graph $G$

I want to find a formula for counting the number of subgraphs in a given graph $G$ with adjacency matrix $A$. The subgraph I want to count its number of occurences is of the structure above. So my ...
• 123
97 views

### How can one efficiently group the nodes of a directed acyclic graph to make collective nodes?

The adjacency matrix $A$ of the transitive closure of a directed acyclic graph can have a `checkerboard' pattern like A = \begin{pmatrix} 0 & ? & ? & ? & {\bf a} &...
• 139
114 views

538 views

### Why isn't this graph bipartite?

This is a very silly question but I can't seem to figure it out. Let $G$ be the graph with 6 nodes and 3 edges where 1 is connected to 4, 2 to 5 and 3 to 6. Le $U = \{1,2,3\}$ and $V=\{4,5,6\}$. Then ...
194 views

### Eigenvector of a $1D$ Path/Grid Graph

Let $A$ be the $N\times N$ adjacency matrix of a 1D grid graph (also called path graph?) of size $N\times 1$. this can be seen as a discrete line of $N$ connected vertices: I know that the ...
• 135
1 vote
100 views

### Eigenvalues for block-tridiagonal adjacency matrix with "rays"

I'm looking for closed-form expressions of the eigenvalues of the following adjacency matrix: M = \begin{pmatrix} A & B^T & 0\\ B & A & C^T\\ 0 & C & A \end{...
• 71
1 vote
77 views

### Sum of pairwise distance after applying normalized adjacency matrix to values

I have $N$ values defined on a graph with $N$ nodes called $x_i$ for node $i$. I define the pairwise distance between these values as follow: $D(x) = \frac{1}{2}\sum_{i,j}a_{ij}||x_i - x_j||_2$ Now, ...
• 550
53 views

### Adjacency Matrix of d-regular graph [duplicate]

"If 𝐴 is the adjacency matrix of a 𝑑-regular graph, then any row of 𝐴 contains exactly 𝑑 1’s. Thus, the vector 1𝑛=1,1,…,1 is an eigenvector of 𝐴 with eigenvalue 𝑑." How do we know ...
Let $G = (V, E)$ be a sparse oriented graph with $n$ vertices (i.e. no loops, no multi-edges, about 1-5% of all possible $n\cdot(n-1)/2$ edges are present). The value of $n$ is about $100$. Let $A$ be ...