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

How to measure the similarity between two weighted graphs?

I have two undirected graph networks and each edge of these networks are weighted through the Pearson Correlation Coefficient values.(Both of these networks have same nodes) I would like to quantify ...
1
vote
0answers
29 views

isomorphic adjacency matrices to one matrix

I need to generate lots of graphs to train my code. But it didn't have any impact if training graphs are isomorphic. So I need to eliminate isomorphic graphs to save time. For this reason, now I'm ...
1
vote
1answer
29 views

How would you define this conditions on a simple undirected and connected graph?

I am stuck on this problem. It is about a simple, undirected and connected graph G on N nodes. It says to consider two vertices u and v s.t. A(u,v) = 0 (with A being the adjacency matrix for G) $$\...
1
vote
1answer
35 views

What's the $2N-$power of adjacency matrix $A$ of a directed tree?

Suppose you have a directed tree with root $v$ and let $A$ be its adjacency matrix. Assume that the number of vertices is $N$. Compute $A^{2N}$. I know that the $n-$th power of an adjacency matrix ...
0
votes
0answers
49 views

Counting walks in combinations of graphs

Consider $A_n$, the collection of all $n\times n$ adjacency matrices where every element can be $1$ or $0$ $A_1 = \begin{pmatrix} 1 \end{pmatrix}, \begin{pmatrix} 0 \end{pmatrix} $ $A_2 = \begin{...
1
vote
1answer
19 views

Complete directed graph 4th and 5th powers of adjacency matrix

Start with a complete graph $K_n$ and assign each edge a direction or delete the edge. Then consider the 4th and 5th powers of the adjacency matrix $A$. Am I correct in thinking that the trace of $A^...
1
vote
1answer
38 views

Adacency matrix of a line digraph

Let $G$ be directed graph with adjacency matrix $A$ and let us assume that $A$ is primitive, i.e. there exists $N\in\mathbb{N}$ such that $(A^N)_{i,j}>0$ for all $i,j$. Let now $L(G)$ be the line ...
2
votes
1answer
46 views

Show that all eigenvalues of a graph $G$ a are equal to $0 \iff G$ is a null graph

I have an idea that I think may work for the first direction, but not quite sure. Can anyone help? Here is my initial idea: Assume all eigenvalues of $G$ are $0$. Then, all eigenvalues $\...
0
votes
0answers
43 views

How is the adjacency matrix of a directed graph normalized?

For an undirected graph with adjacency matrix $A$, it is straightforward to define the normalized adjacency matrix as $$ A'=D^{-1/2}AD^{-1/2}$$ where D is the diagonal matrix of degrees of the nodes ...
0
votes
0answers
25 views

Decomposition by eigenspaces exists simultaneously between two matrices

I am studying the relation of the symmetric matrix and its eigenvalues and eigenvectors to understand the graph features from its adjacency matrix. Suppose that matrix B with size n whose elements ...
0
votes
0answers
51 views

spectral radius of an adjacency matrix $A_n$

Hi gals working in a quite crazy problem that our linear algebra teacher threwed at us out of nowhere, we have to give a proof of a formula for the spectral radius of these adjacency matrices, or in ...
0
votes
0answers
10 views

Given an adjacency matrix of potential edges and a goal pagerank is there a way to remove edges to match the pagerank?

Given an adjacency matrix, $A$, and a goal pagerank vector, $\vec g$, is there a way to remove edges from $A$ so that the pagerank of the modified $A$ is as close as possible to $\vec g$? Perhaps ...
0
votes
0answers
9 views

Distance-Regular Graphs (resources)

I am beginning to research distance-regular graphs and adjacency algebras to prepare to write my thesis. I currently am reading a paper on the topic but it skips a lot of the details. Could someone ...
0
votes
1answer
44 views

How to see if a graph with two coloring has a monochromatic triangle?

Lets say you have an adjacency matrix version of K6 graph colored red or blue. How do you determine if there is a monochromatic triangle. For example, ...
1
vote
1answer
42 views

Solving Labyrinth maze using Dijkstra and adjacency — Alphabet Soup

I've been trying to solve the following problem using adjacency matrix to find the shortest path between the entry and the exit of this labyrinth. The trick on this is that you can't exit a node using ...
0
votes
2answers
39 views

Directed graph and cycles

Reading this article on graph cycles, then we have that for a (undirected?) graph G, given A as adjacency matrix $trace(A^i) \ne 0 \iff $ exists a cycle of lenght i in G Does the same applies to a ...
6
votes
1answer
111 views

Finding a symmetric adjacency matrix closest to a given (non-symmetric) adjacency matrix

I am trying to solve a problem on graphs, which I have reduced to the following optimization problem in matrix $X \in \{0,1\}^{n \times n}$ $$\begin{array}{ll} \text{minimize} & \| X - A \|_F^2\\ ...
13
votes
3answers
325 views

Spanning forests of bipartite graphs and distinct row/column sums of binary matrices

Let $F_{m,n}$ be the set of spanning forests on the complete bipartite graph $K_{m,n}$. Let $$S_{m,n} = \{(r(M), c(M)), M \in B_{m,n} \}$$ where $B_{m,n}$ is the set of $m \times n$ binary matrices ...
0
votes
0answers
26 views

Conjugate adjacency matrices

Suppose $G_1$ and $G_2$ are two finite undirected simple graphs, such, that their adjacency matrices are conjugate over $\mathbb{Z}_2$ (as their only possible entries are always either $0$ or $1$, we ...
1
vote
0answers
238 views

Calculating the Distance Matrix from Adjacency Matrix

How would I calculate the distance matrix of a connected, simple and undirected graph from the adjacency matrix? I have 56 nodes, if that is helpful, and would need to the answer to return an array. ...
0
votes
1answer
27 views

Proof and notations

I was reading this proof, and I do not know what does E stands for, could you help me please? Theorem: Raising an adjacency matrix A of simple graph G to the n-th power gives the number of n-length ...
0
votes
1answer
65 views

Graphs with zero eigenvalues

I search about known graphs have spectrum with the most zero eigenvalues respect to their adjacency matrix. I know null, complete, bipartite and cocktel party graphs. Any kind of suggestion is ...
0
votes
1answer
76 views

Graphs with rational eigenvalues

Let $A$ be the adjacency matrix of a graph with eigenvalues $\lambda_i$. My questions are: Is there any assumption/conditions for a graph to have all rational eigenvalues ($\lambda_i \in \mathbb{Q} \;...
4
votes
1answer
65 views

Finding Euler path using powers of adjacency

Context: I'm studying an introductory course to Discrete Applied Mathematics, and am new to the context of graphs. Knowing that a graph can be represented as an adjacency matrix, say we have the ...
0
votes
0answers
16 views

How to combine multiple small connectivity matrices into one?

I have two connectivity matrices m1 and m2 of nodes 1 and 2 respectively. m1 = [0 50 3 20 4 30] m2 = [1 20 6 10] In each matrix, the ...
2
votes
1answer
61 views

Matrix algebra needed to derive tricky equation… Trophic levels and networks!

Imagine a food web (a directed, acyclic network) where the nodes are species and the edges represent predator-prey relationships. Prey nodes have an edge directed to the predators that eat them. ...
0
votes
1answer
82 views

What properties does an adjacency matrix have for triangular mesh of a sphere?

Given an adjacency matrix $M$. Are there any simple properties that $M$ must have such that it represents the triangular mesh of a sphere. (examples are icosohedron, or geodesic spheres). What about ...
1
vote
1answer
57 views

Given a graph G: how to find a formula to determine the number of squares in which a vertex participates?

I should find a formula that, given a certain vertex v1 of a graph G, it returns the number of squares in which v1 participates. I managed to find a solution for triangles, but in the case of squares,...
4
votes
1answer
176 views

Interpretation of Symmetric Normalised Graph Adjacency Matrix?

I'm trying to follow a blog post about Graph Convolutional Neural Networks. To set up some notation, the above blog post denotes a graph $\mathcal{G}$, it's adjacency matrix $A$, and the degree matrix ...
1
vote
1answer
63 views

Calculating PageRank of a Google Matrix

Let $A$ the adjacency matrix of a Web Digraph, with $\{0,1\}$ entries. For sake of clarity, we assume that the matrix is irreducible and without full-zero rows (i.e. no leaf nodes in the graph) . ...
0
votes
0answers
77 views

Rook Chess Graph Representation

I'm doing an exercise where I have an adjacency matrix for the rook's graph. I need to figure out the right graph using its 3x3 adjacency matrix composed of the following values: ...
0
votes
0answers
22 views

Diameter of cyclic directed graph as bound for powers of adjacency matrix

Consider a cyclic directed graph $G$, is it true that the power series computation of its adjacency matrix $M$ can stop after $k$ steps, being $k$ the directed diameter of $G$, "converging" to a point ...
2
votes
0answers
101 views

Intuitive interpretation of eigenvalues of adjacency matrices of graphs.

Simple set up Let $G=(V, E)$ be an undirected, unweighted, graph and let $A_G$ be the adjacency matrix of $G$. Is there a way to interpret the properties of the eigenvalues of $A_G$ to give insight ...
1
vote
0answers
65 views

Is there a way to simplify a graph and still use the powers of the adjacency matrix to find the number of paths from once point to another?

I'm working on a little extra credit for a problem-solving course. Jack is heading home from work on his bike. His home is 3 blocks north and 4 blocks to the east. The intersection one block north-...
1
vote
0answers
346 views

Sum of the degrees of second neighbours of a vertex in a graph

The question is: "Using only matrix formalism find the vector $\pmb{v}$ whose element $i$ is the sum of the degrees of vertex's $i$ second neighbours". My attempt: Let $A$ be the adjacent matrix ...
4
votes
2answers
174 views

Obtaining the adjacency matrix of Cayley graphs

Is it possible to obtain the adjacency matrix of a Cayley graph of $Z_3 \times Z_5$? (Manually or by using a software like GAP). Will there be a pattern for adjacency matrices of Cayley graphs for a ...
0
votes
0answers
33 views

If $A$ is an adjacency matrix of a labeled multi-digraph is the $(i,j)^{th}$ coordinate of $A^n$ the number of directed $n$-walks from $i$ to $j$?

If $A$ is an adjacency matrix of a labeled multi-digraph is the $(i,j)^{th}$ coordinate of $A^n$ the number of directed walks from $i$ to $j$? I know this is true when $A$ is the adjacency matrix of a ...
1
vote
1answer
36 views

What can be said about the coherent algebra of an asymmetric graph?

Maybe as a follow-up to my last question : What can be said about the coherent algebra of an asymmetric graph? I.e. the smallest unital *-subalgebra of $M_n(\mathbb{C})$ closed under Schur (entrywise) ...
1
vote
1answer
51 views

Adjacency algebra of asymmetric graph

What can be said about the adjacency algebra (or coherent algebra) of an asymmetric graph? Is it always $M_n(\mathbb{C})$? If not, what's a counterexample?
2
votes
2answers
194 views

Node ordering permutation based adjacency matrix

I was reading a research paper where I came across this definition of an adjacency matrix based on a node ordering function. I am a beginner in graph theory hence was not able to understand the ...
4
votes
0answers
176 views

What properties does a graph whose adjacency matrix is invertible have?

I was thinking about adjacency matrices, when I realised that an adjacency matrix is nilpotent if and only if there is no cycle in the graph. So, I started wondering: if a graph has an adjacency ...
2
votes
1answer
67 views

Rank of Seidel adjacency matrix?

Seidel adjacency matrix of a graph, $S=[s_{i,j}]_{n\times n}$, with $V=\{1,2,\ldots,n\}$ is defined as follows: $$s_{ij}=\begin{cases} 1 \quad i\nsim j , i\neq j \\-1 \quad i\sim j \\0\quad i=j \end{...
0
votes
0answers
94 views

Regular graphs has exactly one main eigenvalue

An eigenvalue $\lambda_{1} $ is said to be a main eigenvalue if it has an associated eigenvector $x_{1} $ whose sum of entries is nonzero, in other words the projection of $e $, the all ones vector, ...
1
vote
1answer
64 views

Are all n-dimensional hypercube graphs circulant and if so what is their circulant adjacency matrix?

Usually the adjacency matrix representation of the n-dimensional hypercube, $Q_n$, is given as $$Q_n=\begin{bmatrix}Q_{n-1} & I \\ I & Q_{n-1} \end{bmatrix}$$ where $Q_1$ is the adjacency ...
1
vote
1answer
64 views

incidence matrix of a mixed graph

I have read about incidence matrix of a mixed graph but without example. All examples I saw were either for undirected graphs or for directed graphs but not for mixed graph. What will be the ...
2
votes
0answers
37 views

Number of paths in each connected component

I have a feature space consisting of five amino acids in a protein structure. Three of five amino acids $(A, B, C)$ are within some cutoff distance of each other and two amino acids $(D, E)$ are ...
0
votes
1answer
71 views

Determining (parity of) maximum path length from adjacency matrix. Can I avoid having to square?

Setup: I have an undirected (multi)graph $G$ with $n+1$ vertices. Each vertex has degree $\leq 2$, and vertex number $0$ has degree exactly one. What I'm looking for: I know that any graph with ...
0
votes
1answer
34 views

Algebraic Graph Theory - Finding eigenvalues

I have H obtained from an even cycle $C2k$ for $k>=2$ by adding edges joining vertices at a distance two in $C2k$. I need to show that $A(H)=A(C2k)^2+A(C2k)-2I$ where $A=A(G)$ denotes the ...
2
votes
1answer
55 views

A subclass of regular graphs defined by a property of eigenvectors

I am looking for the largest possible class of regular graphs such that it is possible to form a basis out of the eigenvectors of the graph's adjacency matrix with elements of each vector having the ...
1
vote
1answer
48 views

Is the graph formed by GP series of adjacency matrix, Eulerian?

Suppose I have a Graph G(V,E) and A is the adjacency matrix of G. The graph thus formed by creating a GP series of adjacency matrix $P=A+A^2+A^3+....+A^{n-1}$ Is this graph Eulerian? A is such ...