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

0
votes
0answers
15 views

Known results on the relationship between automorphisms and spectrum of a graph?

I recently saw this post from Ed Pegg on Math Stack Exchange about integral graphs with trivial automorphism groups. I am interested in trying to construct smaller such graphs - at the very least, I ...
3
votes
0answers
87 views

Integral identity graphs — smallest example

From Paulus Graphs. "The (25,2)-, (25,4)-, and (26,10)-Paulus graphs have the apparently rather unusual property of being both integral graphs (or asymmetric) and identity graphs (a graph spectrum ...
0
votes
0answers
23 views

The best known bounds for spectral radius of a graph

There are many bounds for the spectral radius of graphs in terms of no. of vertices, maximum degree, chromatic number etc. I wish to know till date what are the best lower and upper bound for the ...
2
votes
1answer
53 views

How to find eigen values of the above matrix

How to find all the eigen values of the graph (Laplacian): $G=(V(G),E(G))$ where $V(G)=\{1,2,\ldots n\}$ and $E(G)=\{(i,i+1):1\le i<n\}$ On finding the Laplacian Matrix of the graph I found that ...
0
votes
0answers
29 views

How to prove the following fact regarding the second eigen value

I am having trouble regarding the Min-Max Theorem. If $A$ is a symmetric matrix and $\lambda_1\le \lambda_2\le\ldots \le\lambda_n$ be the eigen values of $A$ then by Min-Max Theorem we get $\...
0
votes
0answers
7 views

How to show this inequality

Suppose $0=\lambda_0\le\lambda_1\le \ldots \le\lambda_n$ be the eigen values of the normalized laplacian of a graph $G$. Show that $\lambda_1\ge \dfrac{1}{D\text{vol}G}$ where $D$ denotes the ...
0
votes
1answer
31 views

How to find the eigen values

How to find the eigen values of the graph having vertex set as $\{1,2,.......n\}$ and edge set as $\{(l,l+1)\}$ $ \cup (1,n)$ ? where $1\le l \le n$. Here I am considering the Laplacian matrix of ...
1
vote
1answer
19 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
1answer
28 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
18 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 $A$...
3
votes
1answer
129 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. $K_{...
0
votes
0answers
12 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
26 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
56 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 $n-1$...
0
votes
1answer
27 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
36 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 $G$...
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
32 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
47 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
16 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
60 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
22 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
45 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
41 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
40 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
77 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
66 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
50 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
160 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
46 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
45 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
23 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
25 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
51 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
103 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
34 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
22 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 $$G(x,a)=\frac{1-x^2}{1-...
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) ...