Questions tagged [adjacency-matrix]
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
0
votes
0
answers
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
0
votes
0
answers
32
views
Determinant of involving adjacency matrix of subgraph
Let $A$ be the adjacency matrix of a graph $G$ labelled $\{x_1,\cdots,x_n\}$. Let $B:=(I-\frac{1}{2d}A)^{-1}$ where $d$ is a positive integer.
Then let $A'$ be the adjacency matrix of the graph $G\...
- 1,451
0
votes
1
answer
22
views
Finding path lengths by the power of adjacency matrix of an undirected graph
The same question was asked almost 7 years ago. It turned out to be a matter of terminology in different textbooks between the terms "path" and "walk". While the answers addressed ...
- 103
0
votes
0
answers
41
views
The number of very small eigenvalues of a adjacency matirx
When I calculate the eigenvalues of the adjacency matrix of a graph, which has 34 nodes and 78 edges, I found that there are many eigenvalues close to zero, like, $3.52059077e-16$.
The question is ...
- 11
1
vote
0
answers
31
views
Analogy between graph laplacian and continuous laplacian
The graph Laplacian is ussually defined as $L=D-A$, where $D$ is the degree matrix and $A$ the adjacency matrix.It gets its name from being the discrete analog of the Laplacian operator from calculus.
...
- 11
-1
votes
1
answer
27
views
How to calculate the number of 1 × n*n binary matrices which have no adjacent ones by column, with exactly k ones for large n
How to calculate the number of 1 × n*n binary matrices which have no adjacent
ones by column only, with exactly k ones for large n. No adjacent 11 allowed.
ex: 1 by 9(n=3), k = 3 ones, no adjacent 11.
...
- 1
0
votes
1
answer
66
views
Will the diagonal elements of transitive closure matrix of a 'graph' always be 1?
(CAUTION- PLEASE DO NOT TAKE MY QUESTIONS VERY SERIOUSLY.
I received a ban from asking questions,I don't know what to say really,I am just a student trying to learn,not a professional mathematician,...
0
votes
0
answers
50
views
Prove or disprove that a matrix has all elements in between (-1,1)
Let $X$ be an $N\times K$ real matrix and consider the $N\times N$ symmetric and positive definite matrix $\Theta = X(I + X'X)^{-1}X'$. It is not too difficult to prove that all elements of $\Theta$ ...
- 51
7
votes
1
answer
143
views
Who first noted that entries in the powers of an adjacency matrix of a graph count the number of walks on the graph?
The Wikipedia article on powers of an adjacency matrix presently (as of 2022) notes the neat combinatorial fact that, given an adjacency matrix $A$ of some graph, entries of the $n$th power of the ...
- 353
0
votes
0
answers
57
views
Global efficiency for weighted directed graphs?
I would like to compute the global efficiency of a weighted directed graph. When looking the appendix of Rubinov & Sporns (2009) it seems like there's no difference in the computation:
$$
E^\text{...
- 101
0
votes
0
answers
50
views
Is there an algorithm for computing the independence number or the girth of a graph based on its adjacency matrix?
In this question, "graph" means a non-oriented, simple graph with no loop and no label on the edges or vertices.
For a graph $G=(V,E)$ with vertex set $V = \{v_1,\ldots , v_n\}$, the ...
- 2,585
0
votes
0
answers
24
views
Math operator for disconnection in adjacency matrix?
So I'm implementing the model of a Telecommunication Network as a mathematical network object. Lets say my adjacency matrix is $M$ and its $M_{ij}$ element is 1. So, to simulate a disconnection, I ...
1
vote
0
answers
47
views
How to predict edges of a tree which also occur in the inverse of the tree.
I have a tree with an invertible adjacency matrix. I know a tree has a invertable matrix if the tree has a unique perfect matching.
I take the inverted adjacency matrix of the tree and replace all -1 ...
- 11
3
votes
2
answers
146
views
Adjacency matrix for soccer ball (football)?
Does anyone have a ready reference to the adjacency matrix for the truncated icosahedron (soccer/football)?
(In my retirement, I’m reviewing some of my college maths, and adjacency matrices have ...
- 133
0
votes
0
answers
28
views
Why Laplacian algebra instead of Adjacency algebra?
I'm reading the paper `New bounds for the max-$k$-cut and chromatic number of a graph' by E.R. van Dam and R. Sotirov. In this paper, the authors attempt to find a new bound for the max-$k$-cut ...
0
votes
0
answers
49
views
How to deal with changing "number" of nodes in Adjacency Matrix
I am new to algebraic graph theory and my question may be naive: Adjacency matrix (AM) captures well the connection space between nodes of a graph - connections can easily come and go, where new ones ...
- 103
1
vote
0
answers
89
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}$ ...
- 111
0
votes
0
answers
48
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 ...
- 736
1
vote
0
answers
34
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 [1], to calculate the $(H)$-...
- 279
0
votes
0
answers
22
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 ...
0
votes
1
answer
310
views
Graph theory with trees and adjacency matrix [closed]
For $n \in \Bbb N$ we define the set $\Bbb Z_n = \{1, 2, \ldots , n - 1\}$ and on this set we define the modular product as follows:
For $x, y, z \in \Bbb Z_n : (x\cdot y = z) ⇔ (x\cdot y \equiv z \...
- 1
0
votes
0
answers
517
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
1
answer
511
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
0
votes
1
answer
30
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
\begin{equation}
A = \begin{pmatrix}
0 & ? & ? & ? & {\bf a} &...
- 119
3
votes
0
answers
109
views
Visual analysis of adjacency matrices
Given a simple graph $G$ and its adjacency matrix $A$, one may naturally consider the following graph $A_G$:
$V(A_G)=\{(i,j):i<j,a_{i,j}=1\}$
$E(A_G)=\{\{(i,j),(k,l)\}\in2^{V(A_G)}:(|i-k|=1\text{ ...
- 331
0
votes
0
answers
94
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. ...
- 73
1
vote
0
answers
326
views
Number of k-cycles from an adjacency matrix of a graph
Let $G(V,E)$ be a finite undirected graph with an adjacency matrix $A$. As far as I know it holds that that $A^k_{ii}$ gives us the number of walks starting and ending at vertex $i$ and having length $...
2
votes
3
answers
506
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 ...
- 187
1
vote
0
answers
114
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 ...
- 63
1
vote
1
answer
62
views
Eigenvalues for block-tridiagonal adjacency matrix with "rays"
I'm looking for closed-form expressions of the eigenvalues of the following adjacency matrix:
\begin{equation}
M = \begin{pmatrix}
A & B^T & 0\\
B & A & C^T\\
0 & C & A
\end{...
- 51
1
vote
0
answers
58
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, ...
- 530
0
votes
0
answers
30
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 ...
2
votes
0
answers
117
views
Reordering vertices of a graph to make the adjacency matrix a block matrix with band-shaped blocks
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 ...
2
votes
2
answers
569
views
Spectral radius of a graph
I researched about the spectral radius and was confused. There are two definitions.
The spectral radius of a finite graph is defined to be the spectral radius of its adjacency matrix. the spectral ...
- 361
1
vote
1
answer
2k
views
Obtaining the degree matrix from the adjacency matrix
I was unable to find a mathematical operation for obtaining the degree matrix from the adjacency matrix of a given graph.
For a graph $G = (V,E)$, let $A$ be the adjacency matrix of $G$ and let $D \in ...
- 153
1
vote
0
answers
56
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 ...
- 65
2
votes
1
answer
119
views
What is the number of possible simple directed graphs of $n$ elements without 2-cycles and self-loops?
Let $A$ be the adjacency matrix of a graph with $n$ vertices. Let $a_{ij}$ denote the entry in the $i$-th row and $j$-th column.
For a given $n$, how can we compute the number of possible networks, $f(...
- 171
2
votes
0
answers
148
views
Interpretation of Symmetric Normalised Weighted Adjacency Matrix in GCN
Yann Dubois explained very well about the "Interpretation of Symmetric Normalised Graph Adjacency Matrix?".
He defined that adjacency matrix  can be weighted. He also defined that D̂ is ...
- 21
0
votes
1
answer
389
views
Sum of adjacency matrices in connected graph G
If G is connected graph, then show that there is no $0$ element in matrix $A+A^2+A^3+\cdots+A^{n-1}$ where A is adjacency matrix of G, and n number of vertices. If we are looking at element on ...
- 513
1
vote
1
answer
75
views
There are at most three walks of length 4 between any two distinct vertices of the graph G?
The following adjacency matrix given by A represents a graph called G:
$$A = \left[ \begin{matrix}
0 & 0 & 1 & 0 \\
0 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 \\
...
4
votes
2
answers
379
views
Upper bound on the largest eigenvalue of a simple graph
Let $X$ be a simple graph with $n$ vertices and $e$ edges and let $\lambda$ be an eigenvalue of $X$. Show that
$$ |\lambda| \leq \sqrt\frac{2e(n-1)}{n}$$
which is equivalent to
$$n\lambda^{2} \leq 2e(...
- 297
5
votes
1
answer
205
views
What is a non binary adjacency Matrix?
I am going through the implementation of a graph convolutional neural network. I came across a non-binary adjacency matrix in the case of a directed graph.
The particular issue is discussed here in ...
- 53
1
vote
1
answer
123
views
Eigenvalue of d regular graph being 1
Let G be a (2d-1) regular graph, and $(X_1,X_2)$ be a partition of vertices of G s.t. if $v\in X_i$, then $|N(v) \cap X_i|=d$. Prove that one is an eigenvalue of the adjacency matrix of G.
Since 𝐺 ...
- 1,825
2
votes
2
answers
122
views
How to find the determinant of a scaled adjacency matrix?
If $A$ is a $3 \times 3$ matrix and $\det(A) = -1$, what would $\det(\frac{1}{3} \operatorname{adj}(3A))$ be?
I know that $\det(\operatorname{adj}(A)) = \det(A)^{n-1}$, so I guessed it would be $(27 \...
1
vote
1
answer
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
0
votes
1
answer
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
3
votes
1
answer
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
0
votes
2
answers
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
2
answers
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
0
votes
1
answer
283
views
Number of labelled spanning trees in the following graph.
Hi, I have this question in one of my assignments. Normally I would use an adjacency matrix (a very big one) to solve these kinds of questions but the hint makes me believe the professor wants me to ...
- 69