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
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 ...
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
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
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
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
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 ...
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$...
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_{...
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 ...
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 : ...
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)$ ...
0
votes
1answer
20 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 ...
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
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
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
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 ...
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
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
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 ...
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 ...
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 ...
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 ...
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
50 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
27 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
53 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
9 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 ...