# Tagged Questions

24 views

### Tightest upper bound for $\sum_j g_{ij}$ of an adjacency matrix of a graph

If I have an adjacency matrix of a graph $G$ (i.e. $g_{ij}=1$ if $i$ and $j$ are connected and $g_{ij}=0$ if not. $g_{ii}=0$), is there any tighter upper bound on $\sum_{j} g_{ij}$ than just $n-1$ ...
39 views

### How to show a total order is product order

Besides the definition of product order, is there any other way to show that a total order on two sets can induce a product order? Because I want to solve the problem below: For two graphs ...
27 views

510 views

### Parameter for Katz centrality of a graph

I am teaching a course using M.E.J. Newman's Networks. It covers several measures of vertex centrality. One of them is the Katz centrality. Let $G$ be a graph and let $A$ be its adjacency matrix. ...
150 views

### Is there a simple interpretation of the eigenvectors of a graph (visualizable?)?

I want to understand eigenvectors obtain from graphs (adjacency matrices) in an analogous way as they are interpreted from principal component analysis of a set of images, which is easy:Eigenfaces ...
122 views

### Is Eigenvector/eigenvalues of a sub graph similar to the main graph?

In Gephi I visualized a graph to calculate the eigenvalues,then I choose a portion of graph (e.g 6 vertex with their edges) and delete all others. I calculate the eigenvalues again and noticed that I ...
43 views

### maxcut and the minimal eigenvalue

For an adjacency matrix $A$ that represent a graph $G=\langle V,E\rangle$, I need to show that the maxcut is bounded by: $$\mathrm{maxcut} \leq \frac{1}{2}|E| - \frac{|V| \lambda_{\min}(A)}{4},$$ ...
59 views

I have a question related to Lemma 4.2 from this pdf (which is, btw quite a nice exposition of Hoffman Singleton work on the classifications of Moore graphs of diameter 2 and 3.) We are given a $n ... 1answer 96 views ### Possible relation between spectra bounds of two matrices A Laplacian matrix$L\in\mathbb{R}^{n\times n}$, is a symmetric matrix with entries, l_{ij}=\begin{cases} 1=\sum_{i,~ i\neq j} w_{ij} &\mbox{if } i=j \\ -w_{ij} & ... 1answer 165 views ### Eigenvalues of a special block matrix associated with strongly connected graph Definition Let$G=(V,E,A)$be a strongly connected directed graph, where$V=\{1,2,...,n\}$denotes the vertex set,$E$is the edge set, and$A$is the associated adjacent matrix with$0-1$weighting, ... 3answers 1k views ### Significance of eigenvalue When I represent a graph with a matrix and calculate its eigenvalues what does it signify? I mean, what will spectral analysis of a graph tell me? 1answer 3k views ### What do the eigenvectors of an adjacency matrix tell us? The principal eigenvector of the adjacency matrix of a graph gives us some notion of vertex centrality. What do the second, third, etc. eigenvectors tell us? Motivation: A standard information ... 5answers 2k views ### Spectrum of adjacency matrix of complete graph Fooling around in matlab, I did an eigenvalue decomposition of the adjacency matrix of$K_5$. ... 0answers 193 views ### Eigenvalues of regular graphs Could someone give me a hint for exercise 2.iii of these lecture notes? The exercise asks to show that a$k$-regular undirected graph (without loops) whose adjacency matrix$A$has eigenvalues ... 1answer 371 views ### Spielman's proof of graph connectivity I use Spielman's lectures on course Spectral Graph Theory I have few question regarding Lecture 2. The Laplacian, especially Lemma 2.3.1 (Graph connectivity). Please, help me to make it a little bit ... 1answer 177 views ### Two formulas for the minimal eigenvalue of a graph Hello again everybody, I'm reading Fan Chung's monograph Spectral Graph Theory. In it, she has two formulas for the minimal eigenvalue of a graph. She doesn't explain why they're equivalent, and I'm ... 1answer 455 views ### What does the minimal eigenvalue of a graph say about the graph's connectivity? I'm reading Fan Chung's Spectral Graph Theory, and I'm now in chapter 2. There, Chung proves Cheeger's inequality, which is that$2h_G \geq \lambda_1 > h_G^2/2$for any graph$G$. To me, this ... 2answers 246 views ### Graphs with eigenvalues of large multiplicity For a strongly regular graph, there are exactly 3 eigenvalues, all nonzero (I believe). One has multiplicity 1, which means the other two have pretty high multiplicities. There are tables that give ... 1answer 786 views ### Is there any relation between the principal eigenvector of the original matrix and its inverse? This question pop'd up when I was studying graph. I am thinking about the relation between principal eigenvector of adjacency matrix$A$and its inverse$A^{-1}$, do they have any relation? 2answers 267 views ### Why the eigenvectors of the Laplacian of a Ring graph are sinusoids? The eigenvectors of the Laplacian of a Ring graph with$n$vertices are:$x_k(u) = \sin(2\pi ku/n)$and$y_k(u) = \cos(2\pi ku/n)$for$1\leq k \leq n/2$. The explanation according to Spielman's ... 1answer 170 views ### Kinks in the eigenvalue spectrum of short range lattices Take a periodic one-dimensional lattice of size$N$with$2k$nearest neighborers. That is, vertex$i$is connected to$i+1,i+2,...,i+k$and$i-1,i-2,...i-k$(with the understanding that the indices ... 1answer 243 views ### eigen decomposition of an interesting matrix (general case) Lets define:$U=\left \{ u_j\right \} , 1 \leq j\leq N= b^{L},$the set of all different sequences of length$L$where each element of the sequence can be an integer in$\left \{ 0, 1, .., b-1 ...
Lets define: $U=\left \{ u_j\right \} , 1 \leq j\leq N= 2^{L},$ the set of all different binary sequences of length $L$. $V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}2^{k},$ the set of ...