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
0answers
26 views

Is there a non-trivial special orthogonal transform which preserves the diagonal elements of a symmetric matrix with positive entries?

This problem is at the interface of matrix algebra and spectral graph theory. Let $\mathbf{S}$ be a symmetric $n\times n$ matrix, with positive entries $S_{ij}\geq 0$, and $\mathbf{D} = \mathrm{diag}(...
2
votes
1answer
63 views

Chromatic number of graph of subsets of a set [closed]

Suppose set $A$ with $2n$ elements. Construct simple graph $G$ with $\left(\begin{array}{c}2n\\ n\end{array}\right)$ vertices each one represents one of $n$_sized subsets of $A$ .Connect any two ...
0
votes
0answers
9 views

Equality of sum of fractions implies correspondence of terms

I am working in a theorem of Jhonson and Newman about cospectrality and got stucked un this claim. can you help me? $a_i$ and $b_i$ are non negative numbers, $z\in\mathbb{C}$ and $d_i \neq d_j$ for $...
1
vote
0answers
28 views

Graph Laplacian Rank-One update

Can anyone help me prove/disprove this conjecture? Let $G$ be an undirected nonnegative weighted connected graph with $n$ nodes and Laplacian matrix $L$. Also, let $0=\lambda_1<\lambda_2\leq \...
8
votes
0answers
181 views

When a matrix has same eigenvalues of its column-swapped version?

What are the properties needed for a matrix $A$ to have $\mbox{Spec}(A)= \mbox{Spec}(A \cdot P)$, where \begin{equation} P = \begin{pmatrix} 0 & \cdots & 0 & 1 \\ \vdots & \...
0
votes
0answers
25 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$...
0
votes
1answer
17 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
28 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
98 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 ...
1
vote
1answer
24 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
27 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
56 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
30 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
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 ...
0
votes
1answer
33 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 ...
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 ...
3
votes
1answer
130 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_{...
19
votes
1answer
367 views

What is the intuition behind / How can we interpret the eigenvalues and eigenvectors of Euclidean Distance Matrices?

Given a set of points $x_1,x_2,\dots,x_m$ in the euclidean space $\mathbb{R}^n$, we can form a $m\times m$ Euclidean Distance Matrix $D$ where $D_{ij}={\|x_i-x_j\|}^2$. We know a little bit about ...
1
vote
2answers
345 views

Lower bound on the minimum eigenvalue of sum of two matrices

Assume that $A$ is a symmetric positive definite matrix and $B$ is a symmetric (can potentially negative entries). Is the following bound correct? $$\lambda_{min}(A+B)\geq \lambda_{min}(A)+\lambda_{...
0
votes
0answers
16 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
27 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
57 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 ...
4
votes
0answers
39 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 $\mathcal{G}=(\mathcal{V},\mathcal{...
2
votes
0answers
71 views

Spectral gaps of common graphs

I'm looking for the spectral gap of common graphs (alternatively, the mixing time of a (lazy) random walk on these graphs). Asymptotic values are fine. Assume that every node has a sufficient number ...
1
vote
1answer
37 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
19 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
87 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 : ...
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 & ...
2
votes
1answer
29 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
39 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
53 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
24 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)$ ...
42
votes
6answers
3k views

Motivation for spectral graph theory.

Why do we care about eigenvalues of graphs? Of course, any novel question in mathematics is interesting, but there is an entire discipline of mathematics devoted to studying these eigenvalues, so ...
2
votes
1answer
156 views

Connection between the Tutte and characteristic polynomials?

Both the Tutte polynomial $T_G(x,y)$ and the characteristic polynomial $\phi_G(x)$ encode a great amount of structure of the input graph $G$. I've read somewhere that the Tutte polynomial has a kind ...
0
votes
1answer
21 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
61 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 ...
4
votes
1answer
111 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
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 ...
2
votes
1answer
68 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 ...
1
vote
2answers
49 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
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 ...
4
votes
0answers
75 views

Question about Szemeredi's regularity lemma and eigenvalues of a graph

In the context of Szemeredi's regularity lemma, is there any way to relate the eigenvalues of the ambient graph with the densities of an $\epsilon$-regular partition? More precisely, if $V(G) = V_{0}...
1
vote
0answers
24 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 ...
0
votes
1answer
42 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
3
votes
2answers
81 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 ...
1
vote
0answers
41 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 ...
0
votes
1answer
51 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
55 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 ...