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
votes
0answers
8 views

random walk P Markov chain on graph G IFF lamba =-1 is eigenvalue of P [closed]

I'm trying to solve the backward direction right now... i.e. look at adjacency matrix of bipartite graph,see the fomula here: (https://en.wikipedia.org/wiki/Adjacency_matrix#Of_a_bipartite_graph) , ...
0
votes
0answers
10 views

Deriving Adjusted RAND index from difference of Adjacency matrices

Suppose we represent clustering results of $n$ points with an adjacency matrix $A$ where $A_{ij} = 1$ if $n_i, n_j$ share the same cluster and $0$ otherwise (the diagonals are $1$). Let there be an ...
0
votes
1answer
85 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 ...
0
votes
2answers
46 views

Power of adjacency matrix

What does ij element of the k-th power of adjacency matrix for a directed graph, i.e. A^k represent: number of paths with exact k length or number of paths with length k or less than k from i to j?
1
vote
0answers
15 views

Check if there will be graph represented by incidence matrix, hamilton? Draw the graph.

My task is: "Check if there will be graph represented by incidence matrix and is it hamilton graph? Draw the graph." Matix image $$ \pmatrix{0&1&0&1&0&1&1&0\\ 1&...
2
votes
0answers
48 views

Graphs with maximum and minimum Graph Energies

Given a graph $G$ with $n$ vertices, if its adjacency matrix $A$ has eigenvalues $\lambda_1 \geq \lambda_2 \geq . . . \geq \lambda_n$ then the energy is defined as: $$E(G) =\sum_{i=1}^{n} |\lambda_i|.$...
2
votes
1answer
32 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
1answer
16 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
0answers
30 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 ...
2
votes
1answer
62 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 ...
0
votes
1answer
22 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 ...
0
votes
1answer
38 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
1answer
59 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&...
0
votes
0answers
13 views

Degree Matrix of Fully connected graph

https://www.kaggle.com/vipulgandhi/spectral-clustering-detailed-explanation In this blog post about spectral clustering it states that we can just use the Gaussian Kernel directly. "Generally we ...
0
votes
1answer
51 views

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 ...
1
vote
1answer
81 views

Is there a way to count the number of vertices in a connected subgraph S that is part of a larger, disconnected graph G?

I apologize a head of time if this has been answered elsewhere. I have a random graph G, and this graph is disconnected and contains a unknown number of connected subgraphs (not all vertices in G's ...
1
vote
0answers
17 views

Can we write full basis for 2D matrices

I have a Laplacian matrix of a graph with $N$ nodes named $L_1$. We can diagonalize the matrix and write it as follow: $L_1 = U\Lambda U^T = \sum_k \lambda_ku_ku_k^T = \sum_k \lambda_kB_{kk}$ I have ...
0
votes
1answer
36 views

How do I determine which connections form cycles in a directed graph's adjacency matrix?

given a matrix A I know I can perform A^n = path length from j to v for some entry [j,v] to find paths to v. As I perform this iteration for ...
1
vote
1answer
23 views

How to calculate the Beta index of a graph from its adjacency matrix?

A ratio of the number edges to the number of vertices of a graph $G$ is called Beta index of $G$; it is denoted by $\beta$. In the following figure, the number of edges and the number of vertices are $...
0
votes
1answer
43 views

What are the analogous matrix operations of graph union and intersection operations?

I know that a graph can be represented by its adjacency matrix. Graph union and graph intersection are two important basic operations in graph theory. Working with graphs and their operations is good ...
0
votes
0answers
39 views

Renormalization of a graph adjacency matrix

I know for graph adjacency matrix $A$ and degree matrix $D$, the eigenvalues of $I+D^{-1/2}AD^{-1/2}$ are in $[0,2]$ and repeated use of this as a filter will cause the numerical insatbility. I also ...
4
votes
2answers
239 views

If two graphs are isomorphic then will their determinants be equal?

10 vertices graphs G1 and G2 I'm solving the exercises in chapter 2 from Graph Theory with Algorithms and its Applications. So far, for isomorphism I just write all the edges and try to find the ...
2
votes
1answer
105 views

Eigenvalues of complement of regular graphs

So I have encountered the following fact: Let $G$ be a $d$-regular graph with adjacency eigenvalues $\lambda_1\geq...\geq\lambda_n$. Then its complement graph $\bar{G}$ has eigenvalues $n-1-\lambda_1,-...
2
votes
1answer
55 views

Geometrical significance of Graph energy.

The following definition of the energy of graph is taken from an article entitled "Energy of Graphs. A few open problems and some suggestions" by Dragan Stevanovic of University of Nis, ...
3
votes
0answers
25 views

Rank of non-negative matrices

Are there some easy ways to verify conditions on a nonnegative matrix with $0$ diagonal which ensure that it is conditionally negative definite (i.e., $x^TAx \le 0$ for all $x$ with $x^T\mathbf{1}=0$ ...
0
votes
0answers
30 views

What characterizes the adjacency matrix of a tripartite hypergraph?

The adjacency matrix of a graph $G = (V,E)$ is a matrix with $|V|$ rows and $|E|$ columns, in which element $v,e$ is $1$ if node $v$ is adjacent to edge $e$, and $0$ otherwise. In bipartite graphs, ...
0
votes
1answer
53 views

Creating graph from a matrix.

I have an n.n matrix, like the following picture and I want to create a graph that shows me the relationship between them. In this case that is a real case, I have 4 column that contains traffic flow ...
5
votes
1answer
68 views

Vertices in a graph with the same number of closed walks

A graph is called walk regular if the number of closed walks starting from vertex $u$ of length $k$ does not depend on $u$. If $A$ is the adjacency matrix of the graph, this means that $A^k$ has equal ...
0
votes
0answers
30 views

Existence of an equitable partition in a graph

I've been reading several articles about an equitable partition. I haven't seen any criterion to see if a graph has an equitable partition. All results I have seen so far are about starting with ...
0
votes
1answer
21 views

Relation of Adjacency matrices of 2 graphs

Let G be the subgraph of G¯(prime) such that there is an edge between vi ∈ V and vj ∈ V in G if and only if there is at least one edge between vi and vj in G¯(prime). Any tips or hint to solve about ...
1
vote
1answer
41 views

In a bipartite graph the absolute value of any eigenvalue is less than the square root of number of edges.

Let $G$ be a bipartite graph with $e$ edges. How do we show that the absolute value of any eigenvalue $\lambda$ of $G$ (i.e., the eigenvalue of the adjacency matrix of $G$) is less than or equal to $\...
1
vote
1answer
31 views

if $X\mid Y$ follows Bernoulli with parameter $g(Y)$ then what is $E[X]$?

The context is not important for the question but nevertheless here it is: $A$ is the adjacency matrix of a random simple graph (A is symmetric with zero diagonal and with entries in $\{0,1\}$). The ...
1
vote
1answer
26 views

Usefulness of the inverse of $I-A$ in a finite tree network

I am reading a paper which has some graph theory context as well. Specifically, there is a directed-tree $T$ with reversed-edges (i.e., an edge is from a child node to its parent node instead of ...
3
votes
0answers
57 views

“Balanced” graphs and trees

Let $\Gamma$ be a graph with $n$ vertices. Assume for simplicity that there no loops or double edges. Denote by $A$ its (symmetric) adjacency matrix. We say that $\Gamma$ is "balanced" if $$A x= \...
0
votes
0answers
12 views

How to calculate the n-length paths in a graph with multiple types of edges?

I have a large sparse graph, with 5 types of edges. I'd like to find out how many L-length paths there are, which contain at least m edges of type L. My intuition is that I can use the adjacency ...
1
vote
0answers
42 views

What is the interpretation of the normalized adjacency matrix raised to a power?

What the interpretation of the normalized adjacency matrix raised to a power $K$? If we take the exponent of an adjacency matrix we get the number of walks, but what about if we do that for the ...
2
votes
1answer
59 views

Counting a walk $i \rightarrow j \rightarrow k \rightarrow j \rightarrow l \rightarrow j$ in a graph

This paper gives a procedure for counting redundant paths (which I will refer to as walks) in a graph using its adjacency matrix. As an exercise, I want to count only the walks of the form $i \...
2
votes
1answer
42 views

Matrix of paths from graph $G_1$ to graph $G_2$ to graph $G_3$

If $A$ is the adjacency matrix of graph $G$, then it is a well know property that $A^n$ is a matrix where the element $(i, j)$ gives the number of walks of length $n$ from vertex $i$ to vertex $j$. ...
1
vote
0answers
44 views

Motif adjacency matrices for motifs with $\ge 3$ nodes

I've recently discovered this problem that I find very interesting and useful. The existing question also has an insightful answer which was of great help. The problem can be summarized as: "How many ...
0
votes
1answer
144 views

What is the meaning of eigenvalues in adjacency matrices?

Consider a directed, asymmetric Graph $G$ with its adjacency matrix $A_G$. In the context of recurrent neural networks we use the largest eigenvalue of $A_G$ (i.e., spectral radius $\lambda$) as a ...
0
votes
1answer
17 views

Sum over pairs of nodes forming a triangle

Given a simple graph $G=(V, E)$ and a matrix, $C$, describing a property for each pair of nodes, e.g., the adjacency matrix, or the matrix describing the number of common triangles of two nodes. Is it ...
0
votes
0answers
245 views

Common neighbour matrix of a graph

Problem Let $G = (V,E)$ be a simple graph, $A$ its adjacency matrix and let $c(u,v) = |N(u) \cap N(v)|$ be the number of common neighbours of any pair of nodes $u,v \in V$, i.e. $$c(u,v) = \big|\big\{...
2
votes
2answers
255 views

eigenvalues of k-regular bipartite graph adjacency matrix.

I need some help with this proof: Let G be a k-regular graph. prove that: a) If G is bipartite then -k is an eigenvalue of G's adjacency matrix. b) If -k is an eigenvalue of G's adjacency matrix then ...
0
votes
2answers
332 views

How many cycles in this adjacency matrix?

Consider the $N\times N$ adjacency matrix $A$ such that $$A_{ij}=\begin{cases} 1, &\; \; (i\leq n \;\text{ or }\; j \leq n), \;\; i\neq j \\ 0, & \; \; \text{otherwise}\end{cases} $$ for some ...
1
vote
1answer
385 views

Largest eigenvalue of the adjacency matrix of a graph

Let $G$ be a connected graph with $n$ vertices and $m$ edges. Assume that $\lambda_1$ is the largest eigenvalue of adjacency matrix of $G$. I know that $\lambda_1\geq 2m/n$ with equality holding if ...
0
votes
0answers
23 views

Calculate condition number

For $L1$ And $L2$: $L2=D-A(L1+I)^{-1}$ $L1=D-A$ Can we prove that: condition number of $L2$ < condition number of $L1$ ? if yes, how? Where $D$ is an in degree diagonal matrix and $A$ is an ...
0
votes
0answers
38 views

Find average node distance from Adjacency matrix

Given a general non-directional graph with no multi/self links and $N$ nodes represented by Adjacency matrix $A$, how can I determine the average distance: $$\bar{d} = \frac{1}{N}\sum_{i=0}^{N}{d_i}$...
1
vote
1answer
83 views

On the multiplicity of the second largest eigenvalue of adjacency matrix

Let $G$ be a connected, finite, simple, undirected and vertex-transitive graph with $N$ vertices. Denote by $\mu_0> \mu_1\geq \dots \geq\mu_{N-1}$ all eigenvalues of the adjacency matrix associated ...
0
votes
1answer
21 views

Is the following condition NASC for connectivity of a graph?

Is the statement true that a graph $G$ with $n$ vertices is connected iff $(A+A^2+...+A^n)$ has no $0$ entry,where $A$ is the adjacency matrix of $G$.I have tried to prove it but I could not conclude ...
1
vote
1answer
41 views

Do isomorphic graphs have same adjacency matrix upto some permutation of both rows and columns?

Suppose $2$ graphs are isomorphic,then if we write the adjacency matrix of the second graph by arranging the rows and column in similar way to corresponding arrangement of vertices of first graph,then ...