All Questions
Tagged with adjacency-matrices graph-theory
19 questions
2
votes
0
answers
55
views
Regularize a graph while embedding the spectrum of adjacency matrix
Given an irregular graph $G$ whose maximum degree is $d$, I am interested in producing a new graph $G'$ which is regular and has the spectrum of the adjacency spectrum of $G$ embedded in the spectrum ...
- 21
6
votes
1
answer
515
views
Non-diagonalizability of the adjacency matrix of a directed graph
Let $G$ be a directed graph with no multiple edges or loops and let $P_i$ be its vertices. Let $A$ be the corresponding adjacency matrix of $G$, i.e. $a_{i,j}=1$ if and only if there is a directed ...
- 4,058
0
votes
0
answers
73
views
Show that two matrices are strongly shift equivalent
The following question is from Introduction to dynamical systems, written by Michael Brin and Garrett Stuclk.
Given two non-negative integer square matrices $A, B$, we say $A, B$ are elementarily ...
- 307
2
votes
1
answer
521
views
Solution to the sum of k-step path lengths between node pairs in directed weighted graphs
In a non weighted graph, the adjacency matrix ($A$) raised to the power $k$ will return the number of k-step paths between nodes $i$ and $j$ at the entry $a_{ij}$. Is there an equivalent for weighted ...
- 23
2
votes
0
answers
157
views
Formulas to determine the value of graph energy with addition or deletion of edges
If $G$ is a graph, then the graph energy of $G$ denoted by $E(G)$ is defined as the sum of absolute values of eigenvalues of the adjacency matrix of $G$. It is known that $E(G)\geq E(G-v)$, where $ ...
- 203
5
votes
0
answers
513
views
Computing adjacency matrix eigenvalues by counting closed walks
Let $G$ be a finite undirected graph. A closed walk in $G$ is a walk from any vertex of $G$ to itself. It is relatively straightforward to show that the total number of closed walks of length $k$ in $...
- 24.2k
24
votes
6
answers
2k
views
Factorization of the characteristic polynomial of the adjacency matrix of a graph
Let $G$ be a regular graph of valence $d$ with finitely many vertices, let $A_G$ be its adjacency matrix, and let $$P_G(X)=\det(X-A_G)\in\mathbb{Z}[X]$$ be the adjacency polynomial of $G$, i.e., the ...
- 47.4k
3
votes
1
answer
163
views
Traces and closed walks that do not close before their time
Let $A$ be the adjacency matrix of a graph. Then, as is well-known and trivial to show, $\mathrm{Tr} A^k$ equals the number of closed walks of length $k$.
Is there a similar way to express (a) the ...
- 20.2k
1
vote
1
answer
847
views
Do there exist graphs whose adjacency matrix is positive semi-definite? [closed]
If so, could you provide examples and specify the conditions under which this occurs? Thank you in advance
1
vote
1
answer
1k
views
Significance of the Eigenvalues of the adjacency matrix of a weighted di-graph
I'm currently running a simulation on a bunch of randomly generated points, each with two randomly selected 'partners' from the set of points. In the simulation the points try to move such that they ...
- 13
2
votes
2
answers
234
views
Adjacency matrix of total graph
Is there a nice way of relating the adjacency, incidence , Laplacian matrices and other matrices associated to a graph of a total graph with its original graph, or, say, at least relating that of the ...
- 2,089
5
votes
1
answer
425
views
Determining the primitive order of a binary matrix
Let ${\bf A}_n$ be an $2n \times 2n$ matrix that is defined as follows
$$
{\bf A}_n=\left(
\begin{array}{c}
0&0&\cdots&0&0&0&0&1&1\\
0&0&\cdots&0&0&...
- 313
2
votes
1
answer
316
views
When does a row standardized adjacency matrix have a real spectrum?
A colleague in spatial statistics was looking at a map with about 600 regions. For the application she's considering, the induced adjacency matrix had some undesirable properties (where two regions ...
- 6,001
1
vote
0
answers
105
views
Primitivity of $AA^\top$
Let $A\in\mathbb{R}^{n\times n}$ be a non-negative and irreducible matrix. Consider $B:=AA^\top$. It can be proved (I can post a proof if needed) that the following condition is necessary and ...
- 2,712
2
votes
0
answers
159
views
Which functions preserve the connectivity of graphs/components?
I am somewhat stuck working on an issue and would really love some guidance. I will state the problem, my current state and what led to it in case the solution lies beyond where I was looking
The ...
- 21
8
votes
3
answers
8k
views
Spectrum of an adjacency matrix
The adjacency matrix of a non-oriented connected graph is symmetric, hence its spectrum is real.
If the graph is bipartite, then the spectrum of its adjacency matrix is symmetric about 0. A few ...
- 3,388
11
votes
5
answers
2k
views
Which directed graphs have a normal adjacency matrix?
I am working on a problem in matrix analysis and I am looking for certain types of normal matrices. I suspect that these "special" normal matrices arise as adjacency matrices of certain graphs. My ...
- 3,699
1
vote
2
answers
175
views
Is there a name for this operation on graphs - e.g. duplication, Kronecker product of graphs?
I am revising a paper where one of the operations performed on a undirected graph with no loops, is to take each vertex, and split it into two vertices, and take each edge and replace it with 4 edges: ...
- 129
-3
votes
1
answer
336
views
adjacency matrix of random geometric graphs [closed]
Consider a graph with N nodes. All nodes are distributed as a Poisson point process with density of λ in a L*L area. There is an edge between two nodes if and only if the distance between them is less ...
- 35