For questions related to the study of properties of a graph in relationship to the spectral properties of some associated matrix.

learn more… | top users | synonyms

1
vote
1answer
7 views

Vertex Cosine Similarity of a weighted graph

I'm trying to calculate the vertex cosine similarity of a weighted directional graph, however struggling to understand the concept. While I understand the methodology for simple and directed graphs, ...
0
votes
0answers
7 views

Spectral Graph Theory :Cartesian product of Laplace Matrix

Let $G\times H$ be the Cartesian Product of $G$ and $H$. Determine $L(G\times H)$ in terms of $L(G)$ and $L(H)$ where $L(G) $ denotes Laplacian Matrix of $G$. Also find the eigen ...
1
vote
0answers
15 views

How to prove the following statement for a simple graph to be bipartite?

Let $G$ be a simple graph on finite number of vertices and $A$ be its adjacency matrix. Suppose, if $\lambda$ is an eigenvalue of $A$ with multiplicity $k$, then $-\lambda$ is also an eigenvalue of ...
3
votes
1answer
115 views

Eigenvalues of “almost” complete bipartite graph ?!

Please note that I'm just looking for a partial answer to this question. Definition Let $G=U\cup V$ be a bipartite graph, where $U$ and $V$ are disjoint sets of size $p$ and $q$, respectively. ...
0
votes
0answers
10 views

Optimizations in Laplacian Eigenmap/Graph Embedding?

Note -- this question is closely related to this question that asks why the optimization constraint has to be $y^TDy=1$ instead of simpler $y^Ty=1$. Maybe answering this question will automatically ...
0
votes
0answers
15 views

undirected unweighted graphs having $1$ as an eigenvalue

I want to know whether the class of graphs whose spectrum contains $1$ is classified? By spectrum of a graph, we mean the set of eigenvalues of the adjacency matrix of the graph. Please suggest some ...
0
votes
0answers
23 views

How to find the characteristic polynomial for the following graph G

What is the closed form of characteristic polynomial (adjacency matrix) for the following graph $G$: With the help of eigenvectors, I found that $4$ eigenvalues of $G$ are that of $P_4$ and $6$ ...
1
vote
1answer
55 views

On the eigenvalues of “almost” complete graph ?!

Preliminaries: Let $K_n$ be the complete graph on $n$ vertices. $|E(K_n)|=\frac{n(n-1)}{2}$. It's well known that the eigenvalues of $K_n$ are $n-1$ with multiplicity 1, and -1 with multiplicity ...
0
votes
1answer
24 views

Spectrum of Line graph of regular graph

Definition: Let $G$ be a graph, the line graph of $G$ denoted of $L(G)$ is defined as follows: -The vertices of $L(G)$ are the edges of $G$ -Two vertices of $L(G)$ are adjacent iff their corresponding ...
1
vote
1answer
31 views

On the multiplicity of the eigenvalue 0 of the adjacency matrix?

Preliminaries: -Laplacian matrix of graph $G$ is defined as follows: $$L=D-A $$ where $D$ is the degree matrix and $A$ is the adjacency matrix of the graph. -The algebraic connectivity of a graph ...
0
votes
0answers
18 views

How to prove the following facts regarding the matrix

Let $X$ be a connected graph on $n$ vertices and $n$ edges. Let $Q$ be its edge incidence matrix.If $T\subset \{1,2 ,n\}$ with $|T|=n-1$ then $\det (Q[1,2 ,n-1\mid T])=^+_- 1$ if and only if the ...
0
votes
0answers
86 views

The eigenvalues of a graph

Let $m\geq 3$, $n,k \geq 1$, and $m\leq k$. Consider the graph $G=G(m,n,k)$ as follows: $$ V(G)= \lbrace a_i : i\in \mathbb{Z}_m\rbrace \cup \lbrace b_i : i\in \mathbb{Z}_n\rbrace \cup \lbrace c_i : ...
2
votes
1answer
27 views

Prove Cycle Graphs are never hyper-energetic.

The energy of a graph G, is defined as $$\varepsilon(G)=\sum_{i=1}^{n}\left|\lambda_i\right|$$ where $\lambda_i$ are the eigenvalues associated with the adjacency matrix of the Graph. The energy of a ...
0
votes
1answer
31 views

Number of regular tournaments

A regular tournament is a tournament where each player has the same number of wins. Since each player plays $n-1$ games, a regular tournament must have an odd number of players. My question is - 'how ...
4
votes
2answers
43 views

Geometric intuition of graph Laplacian matrices

I am reading about Laplacian matrices for the first time and struggling to gain intuition as to why they are so useful. Could anyone provide insight as to the geometric significance of the Laplacian ...
1
vote
0answers
23 views

How to prove the determinant of resistance matrix $R$?

Let $G$ be a connected graph with $n$ vertices, $R$ be the resistance matrix of $G$, $\tau$ be the $n\times 1$vector with components $\tau_1,\tau_2,...\tau_n$,and $\tau_i=2-\sum_{j\thicksim i} r(i,j)$ ...
0
votes
1answer
15 views

Fiedler vector for weighted graphs

The second smallest eigenvalue of the Laplacian matrix of a (connected) graph is known as the algebraic connectivity of a graph and the corresponding eigenvectors are known as Fiedler vectors. I got ...
0
votes
1answer
55 views

Algebraic Graph Theory: What is an integral eigenvalue?

I'm having some trouble with the an problem out of Bondy and Murty's Graph Theory (2008): 1.1.21 b) Show that rational eigenvalues of a graph are integral. I understand that this is a statement ...
0
votes
0answers
17 views

Commuting weighted Laplacians

During my research I am concerned with the problem of finding commuting weighted Laplacian matrices (w.r.t finite simple weighted graphs on the same vertex sets). My question is about necessary ...
4
votes
1answer
109 views

Spectral radius of “almost” regular graph ?!

The answer to this question could be trivial. The Graph Let $G$ be graph formed of two $d$-regular connected components. That is, $G= H_1\cup H_2$, where $H_1$, and $H_2$ are $d$-regular and ...
0
votes
1answer
20 views

Whether the attached graphs are isomorphic?

Whether these two graphs are nonisomorphic? They have same number vertices, same regularity, they are cospectral (means: they have same same set of adjacency eigenvalues). I have taken powers of ...
1
vote
0answers
17 views

Recommended overlapping community detection algorithms?

Looking for overlapping community detection algorithm with following properties: undirected unweighted graph potentially overlapping communities good scalability to 1M nodes good intuitive results ...
1
vote
2answers
40 views

nonisomorphic cospectral regular graphs

Is there any non-isomorphic cospectral regular graphs? Please suggest some examples or reference. Cospectral graphs are those graph which possess same set of spectrum.
0
votes
1answer
40 views

Does the leading eigenvalue of a connected undirected graph always increase with an edge addition?

Does the leading eigenvalue always increase with an edge addition to the graph? If so, how can I prove this? Thank you
1
vote
0answers
38 views

Merging two nodes in a directed graph with transitions

Let's say I have $M=\begin{bmatrix}1&2&1\\ 4&2&0 \\ 1& 1& 1\end{bmatrix}$, a $3\times3$ matrix which is the transition matrix or adjacency matrix of a $3$-node graph. I would ...
3
votes
2answers
71 views

Let $A\in M_n(\mathbb R)$ is a non-zero symmetric zero-diagonal matrix and its elements are $0$ ore $1$. What we can say about eigenvalue of $A$?

Let $A\in M_n(\mathbb R)$ is a non-zero symmetric zero-diagonal matrix and its elements are $0$ ore $1$. We know that the eigenvalue of $A$ are real. I'm interesting to know the number of distinct ...
2
votes
1answer
61 views

ELI5: What is spectral graph theory?

I am aware that there is already a similar question here, but unfortunately I find the discussion there to be beyond my grasp. I am looking for an intuitive explanation of spectral graph theory, as ...
0
votes
1answer
49 views

Subgraph of integral graph is also integral??

Background: An integral graph is a graph whose spectrum consists entirely of integers (see [1]). Example: Complete graph $K_n$, since spectrum$(K_n) = (n-1,-1,\ldots,-1)$ Question Is the induced ...
3
votes
2answers
155 views

Fact regarding Kirchhoff's Theorem

Question regarding Kirchhoff's Theorem: If $ L(G)$ denotes the Laplacian of a graph $G$ then Kirchhoff's Theorem states that number of spanning trees in $G$ is equal to $(-1)^{i+j} \det L(i|j)$ ...
1
vote
0answers
33 views

Matrix -tree theorem-How to understand the theorem

I am having trouble understanding Kirchhoff's Theorem. The statement I want to prove is that if $\lambda_1,\lambda_2,...,\lambda _{n-1}$ are non-zero eigen values of $L(G)$ then Number of ...
1
vote
0answers
54 views

On the eigenvalues of bipartite graph?

Definition Let $G=U\cup V$ is bipartite graph, where $U$ and $V$ are disjoint sets of size $p$ and $q$, respectively. The complete bipartite graph denoted by $K_{p,q}$ is bipartite graph where every ...
0
votes
0answers
39 views

Why does solving the Laplace equation on a graph using the method of relaxation get different results than a spectral method?

When I use the method of relaxation to solve Laplace's equation on a graph where the boundary conditions are fixing a set of nodes to either 0 or 1 then the solution ends up being entirely between 0 ...
0
votes
0answers
20 views

spectral density of Guassian random matrix

I am interested in the spectral properties of Gaussian random matrix. I can see the constant dominance (mostly by the two most extreme ones-largest and smallest-) of the extreme eigenvalues in the ...
1
vote
0answers
23 views

The Laplacian spectra of random graph $G(n,m)$ and $G(n,m+k)$

I am currently doing some work related to the eigenvalues of the Laplacian of a graph. Define $\sigma_i=\frac{\lambda_i}{\lambda_2}$, where $0=\lambda_1<\lambda_2\leq\cdots\leq \lambda_N$ is the ...
1
vote
1answer
44 views

Spectrum of k-partite graph

For a given undirected graph, it is known that the signless Laplacian $Q=D+W$ is positive semidefinite, where $W$ is the adjacency matrix and $D$ is the degree matrix. In particular, the smallest ...
6
votes
1answer
96 views

How to read Spectral Theory of Graphs

My background is a course is Linear Algebra -Hoffman,Kunze Graph Theory-Frank Harary I am doing a coursework in Spectral Graph Theory . As I am going through it, I am searching for some ...
0
votes
1answer
27 views

graphs with smallest eigenvalue at least -1

Let $G$ be an undirected simple graph and let $A$ be its adjacency matrix. It is easy to see that $A$ is neither positive semidefinite nor negative semidefinite. I would like to know if there are ...
2
votes
0answers
8 views

Can a graph be recovered from its Bonacich centrality vector?

Let $A$ be the adjacency matrix of a directed graph with $n$ vertices and spectral radius $\lambda$. Let $I$ be the $n \times n$ identity matrix and let $e \in \mathbb{R}^n$ be the vector of 1's. For ...
0
votes
0answers
22 views

Sparsifying a weighted complete graph

Sparsifying a graph $G=(V,E)$ using effective resistance method [as described in http://arxiv.org/abs/0803.0929 ], requires the existence of a Laplacian solver which can be used to calculate the ...
1
vote
0answers
32 views

Spectral radius of perturbed bipartite graphs

I am looking into how perturbation(s) on a bipartite graph affect its spectrum (specifically its spectral radius or largest eigenvalue). Actually I'm not exactly looking into bipartite but the ...
0
votes
1answer
21 views

Are cospectral/non-cospectral non-isomorphic graphs similar?

Suppose you have two adjacency matrices $A$ and $B$ of cospectral but non-isomorphic graphs. Is there a matrix $Q$ such that $$A=Q^{-1}BQ$$ holds? Note if $A$ and $B$ are not cospectral we cannot ...
2
votes
0answers
207 views

Is each edge interpreted like a $2$-cycle?

Let $a_k$ a an eigenvalue of the adjacency matrix $A$ of a planar cubic graph with $n$ vertices. For the returning paths without backtracking we get the generating function of ...
4
votes
0answers
31 views

What does the spectrum of the adjacency matrix of a graph tell you? [duplicate]

I am trying to search for an answer to the following question and I cannot find a straightforward answer. What does the spectrum of the adjacency matrix (set of eigenvalues and their multiplicities) ...
1
vote
1answer
283 views

All Ihara $\zeta$ functions for planar $k$-regular graphs with a given set of faces are equivalent

This sounds like a simple piece of math (which got a long story over time, thanks for reading!) and the consequence seems surprising. At least to me. Here it is: It boils down to comparing two ...
3
votes
1answer
56 views

Trace of hadamard product of adjacency matrices based on eigenvalues

Let $A$ be the adjacency matrix of the simple graph $G_n$. Is there any formula for $\text{trace}(A^3 \circ A^2)$ based on eigenvalues of $A$?
1
vote
0answers
51 views

Semigroup of matrices and expander Cayley graphs

I am interested in proving or disproving that certain Cayley graphs are expander. Let $S$ be the multiplicative semigroup of matrices generated by $A = \left( \begin{array}{cc} a & b \\ 0 & ...
4
votes
0answers
38 views

Multiplicity of 0 eigenvalue of directed graph Laplacian matrix

I am looking for a result (if it exists) for directed graphs relating the multiplicity of 0 eigenvalues of the directed Laplacian matrix. Consider a directed graph ...
0
votes
0answers
10 views

Minimum Degree of Maximally Eigencentral Vertices

In Grassi et al. (2007), they state the following theorem: Let $G(V,E)$ be a connected graph and $A$ its adjacency matrix, with spectral radius $\rho$ and principal eigenvector $x$. Let us ...
0
votes
0answers
34 views

Eigenvalues of graphs

Given an undirected, unweighted graph $G$, let $A_G$ denote the graph's adjacency matrix. I want to understand in what cases there exists negative eigenvalue for $A_G$, for example, any claim of the ...
3
votes
0answers
49 views

sum of the modulus eigenvalues of a matrix A >= B.

Kindly help me to prove/disprove the following statement. Let $A$ be a symmetric matrix of order $n \times n$ with all the diagonal entry equal to $0$, and other non-diagonal entry equal to $k$ ...