# Tagged Questions

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

26 views

28 views

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 ...
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 ...
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, ...
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 ...
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$...
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_{... 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 ... 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$... 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$... 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 ... 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$... 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 ... 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 : ... 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 ... 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 ... 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 ... 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)$... 1answer 23 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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. 1answer 43 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 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 ... 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 ... 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 ... 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 ... 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)$... 0answers 56 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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$...
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 ...