Skip to main content

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.

Filter by
Sorted by
Tagged with
1 vote
5 answers
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 ...
Ian Lee's user avatar
  • 11
1 vote
0 answers
49 views

Is it possible to know the information of edges of the graph from its adjacency matrix's eigen vectors?

Suppose $G$ be a connected simple graph, and $A(G)$ be its adjacency matrix such that $a_{ij}=\begin{cases} 1 ,i \sim j & (ij \in E(G))\\ 0 ,i \not\sim j & (ij \not\in E(G)) \end{...
David's user avatar
  • 398
2 votes
1 answer
36 views

Expectation of the power of random graph's adjacency matrix

I am trying to find the power of the random graph's adjacency matrix. Consider the $2N$ number of nodes, where $N \geq 2$ is a fixed natural number. WLOG, let nodes with index $1$ to $N$ belong to ...
김선우's user avatar
0 votes
0 answers
13 views

In the adjacency matrix of a graph with n vertices and m edges

In the adjacency matrix of a graph with n vertices and m edges, how many rows are at most two by two? How many columns are at most two by two?
user212662's user avatar
0 votes
0 answers
39 views

Homomorphic product of graphs

I was looking into how the eigenvectors of graphs change upon taking products. For instance, the cartesian product of two graphs $G_1 \square G_2$ has eigenvalues $\lambda_i + \mu_j$ for $\lambda_i$ ...
Jeff's user avatar
  • 401
0 votes
1 answer
55 views

Graph $ G $ is bipartite if and only if the eigenvalues of graph $ G $ occur in pairs $ \lambda, \lambda' $ such that $ \lambda' = -\lambda $.

Let $ G = (V, E) $ be an arbitrary graph, and let $ v_i, v_j $ be any vertices of graph $ G $. Let $ A $ be the adjacency matrix of graph $ G $. Prove the following statements: (a) The number of $ v_i,...
ukm2030's user avatar
  • 47
0 votes
0 answers
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 ...
Luke Green's user avatar
2 votes
1 answer
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 ...
Tung Nguyen's user avatar
  • 1,302
0 votes
1 answer
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 ...
innocuous-squid's user avatar
1 vote
1 answer
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 ...
Math101's user avatar
  • 4,653
1 vote
1 answer
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 ...
Chandana Deeksha's user avatar
0 votes
0 answers
73 views

Approximating the trace of the power of a large adjacency matrix

The motivation for this question is counting cycles in directed graphs with millions of vertices. Given a large (not necessarily symmetric) adjacency matrix $A \in \{0, 1\}^{n \times n}$, where $n \...
Vezen BU's user avatar
  • 2,098
0 votes
1 answer
33 views

Source of theorem regarding triangle presence in the graph

I know that there exists a theorem that states the following. Graph $G$ contains a triangle if and only if there exist indices $i$ and $j$ so the both matrices $A_G$ and $A_G^2$ will have nonzero ($i,...
Keithx's user avatar
  • 159
1 vote
1 answer
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 ...
Snowflake's user avatar
  • 326
2 votes
1 answer
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 ...
Snowflake's user avatar
  • 326
2 votes
1 answer
46 views

Inequality for local spectral moments of adjacency matrix

According to this paper, the local spectral moments $\mu_k(i)$ are defined as the $i$-th diagonal entry of the $k$-th power of the adjacency matrix $A$ of a simple graph $G = (V, E)$, i.e., $$ \mu_k(i)...
Bob Aiden Scott's user avatar
1 vote
1 answer
124 views

On the weighted adjacency matrix of a directed acyclic graph (DAG)

A matrix $W \in \mathbb{R}^{d \times d}$ is the weighted adjacency matrix of a directed acyclic graph (DAG) if and only if $$ h(W) = \operatorname{tr} \left( \exp(W \circ W ) \right) - d = 0 $$ where ...
Jackie's user avatar
  • 553
2 votes
1 answer
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 ...
Pablo de la Fuente's user avatar
1 vote
1 answer
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 ...
Salban Nithilaselvan's user avatar
2 votes
1 answer
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$...
Loic Stoic's user avatar
4 votes
0 answers
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}$ ...
beyondzk's user avatar
0 votes
0 answers
94 views

Draw random graph from adjacency matrix

In a circular area of radius $25$ miles, $32$ nodes are randomly placed. The distance $d$ between each pair of nodes can be the following: $R_1 ~: 0 < d \leq 5$ miles $R_2 ~: 5$ miles $< d \leq ...
Fitzgerald Brooks's user avatar
2 votes
0 answers
96 views

Eigenvectors of Kneser graphs [closed]

The eigenvalues of the adjacency matrix of a Kneser graph are known (see https://en.wikipedia.org/wiki/Kneser_graph). Are the eigenvectors known?
GaussJordan's user avatar
1 vote
0 answers
147 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 ...
dual's user avatar
  • 11
0 votes
1 answer
96 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 ...
Moobie's user avatar
  • 103
1 vote
0 answers
54 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 ...
Henry's user avatar
  • 21
1 vote
0 answers
122 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....
PabloVD's user avatar
  • 11
-1 votes
1 answer
60 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. ...
ALLA's user avatar
  • 1
0 votes
1 answer
129 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,...
Rishabh Narula's user avatar
9 votes
1 answer
249 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 ...
Mark S's user avatar
  • 402
0 votes
0 answers
26 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 ...
greyboxdude's user avatar
1 vote
0 answers
48 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 ...
Mäx's user avatar
  • 11
3 votes
2 answers
217 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 ...
Bruce Simonson's user avatar
0 votes
0 answers
75 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 ...
Brian S.'s user avatar
  • 113
1 vote
0 answers
216 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}$ ...
user1051358's user avatar
1 vote
0 answers
68 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)$-...
user56643's user avatar
  • 299
1 vote
1 answer
326 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 \...
hdsa's user avatar
  • 23
1 vote
0 answers
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 ...
11343Student's user avatar
1 vote
1 answer
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 ...
George's user avatar
  • 123
0 votes
1 answer
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 \begin{equation} A = \begin{pmatrix} 0 & ? & ? & ? & {\bf a} &...
user438111's user avatar
3 votes
0 answers
114 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{ ...
Bertrand Haskell's user avatar
0 votes
0 answers
165 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. ...
lakdee's user avatar
  • 95
2 votes
0 answers
874 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 $...
Dominik Farhan's user avatar
2 votes
3 answers
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 ...
Martin Williams's user avatar
2 votes
0 answers
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 ...
Matt's user avatar
  • 135
1 vote
1 answer
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: \begin{equation} M = \begin{pmatrix} A & B^T & 0\\ B & A & C^T\\ 0 & C & A \end{...
JonasB's user avatar
  • 71
1 vote
0 answers
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, ...
user137927's user avatar
0 votes
0 answers
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 ...
christinaf's user avatar
2 votes
0 answers
162 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 ...
Dmitry D. Onishchenko's user avatar
2 votes
2 answers
1k 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 ...
N math's user avatar
  • 361

1
2 3 4 5