# Tagged Questions

**0**

votes

**2**answers

77 views

### Form of the Shannon capacity for Heptagon?

Is the $0$-error capacity of $7$-cycle:
$(1)$ known to be of form $7^q$ for some $q\in \mathbb Q$?

**3**

votes

**2**answers

81 views

### eigenvalue estimate of the adjacency matrix

The adjacency matrix of a nonempty (undirected) graph has a strictly positive largest eigenvalue $\lambda_\max$. A very easy upper estimate for it can be obtained directly by Gershgorin's theorem:
$$
...

**5**

votes

**0**answers

157 views

### (Connected) Cayley graphs of PSL(2,q) from (2,3,n)-triples

Let $G = PSL(2,q)$. I'm interested in the Cayley graphs of $G$ generated by triples $(A,BAB^{-1},B^{-1}AB)$, where $A, B \in G$ are elements of order $2, 3$ respectively: such a triple generates all ...

**7**

votes

**1**answer

196 views

### A conjecture about strongly regular graphs

Let $G \neq K_{v}$ be a $(v,k,\lambda,\mu)$ strongly regular graph. After perusing through Brouwer's tables of parameters I have formed the conjecture $$\lambda-\mu \leq \frac{k}{2}.$$
So far I have ...

**4**

votes

**0**answers

94 views

### Full-rank factorization of the graph Laplacian

Is there a combinatorially meaningful full-rank factorization of the Laplacian matrix of a graph?
The usual factorization $L=BB^{T}$, where $B$ is an oriented incidence matrix, is full-rank if and ...

**5**

votes

**2**answers

221 views

### Roots of matching polynomial of graph

At the end of this preprint, I make the following conjecture concerning the roots of the matching polynomial:
If a graph $G$ is connected and contains a cycle, then the spectral radius of $G$ ...

**8**

votes

**1**answer

168 views

### Spectral lower bounds on the diameter of a graph

There is such a bound, due to Mohar and McKay, using the second-smallest eigenvalue of the Laplacian $\lambda_{2}$:
$$Diam \geq \lceil \frac{4}{n\lambda_{2}} \rceil.$$
This bound is very elegant but ...

**2**

votes

**1**answer

80 views

### Eigenvalues of a graph and its one-edge-delation graph

Let $G$ be any graph with at least one edge and let $e$ be any edge of $G$. Let $G-e$ denote the subgraph of $G$ obtained by deletion of the edge $e$. Assume that $G$ has $n$ vertices.
Suppose ...

**3**

votes

**0**answers

139 views

### Must distinct tree eigenvalues be relatively far apart?

How close to each other can two distinct eigenvalues of a tree be, as a function of the number $n$ of nodes ?
For example, the path $P_n$ exhibits a gap of order $\frac{2\pi^2}{n^2}$ asymptotically ...

**1**

vote

**0**answers

64 views

### interpretation of generalized eigenvalue/vectors in spectral graph theory

Let us say I have a symmetric graph adjacency matrix A, a degree matrix D, a laplacian L (D-A). I have a generalized eigenvalue equation $Av=\lambda Lv$. Does the eigenvalue/vectors produced in this ...

**12**

votes

**3**answers

287 views

### How can I prove that a particular family of graphs is integral?

I'm working with an infinite family of graphs that seems to always have all integral eigenvalues, and I'd like to find some way to prove that (if it's true). Call the graphs $G_{n,k}$ and define them ...

**3**

votes

**1**answer

109 views

### The spectral radius of a modified graph

Let $H$ be a graph and let $G=H \vee K_{1}$ be obtained by creating a new vertex and joining it to every vertex in $H$.
This situation has many different names: $G$ is called the cone or the ...

**0**

votes

**1**answer

123 views

### Which graph topology has the greatest eigenvalue?

I am looking at comparing multiple graph topologies based on their spectra. From the set of all $N\times N$ adjacency matrices, is there any result which points to the adjacency matrix with the ...

**5**

votes

**2**answers

158 views

### Reflexive (hyperbolic) graphs

Is there an effective description of the graphs such that exactly one eigenvalue (of the conventional adjacency matrix) is $>2$ whereas all others are $\le2$?
By "effective" I mean something ...

**3**

votes

**2**answers

375 views

### spectrum of an adjacency matrix

The adjacency matrix of a non-oriented connected graph is symmetric, hence its spectrum is real.
If the graph is bipartite, then the spectrum of its adjacency matrix is symmetric about 0. A few ...

**2**

votes

**1**answer

189 views

### Graph of Grassmannian

Let p be an integer, and let G be the graph $(V=Gr(k,\mathbb{F}_q ^n),E)$
where: $Gr(k,\mathbb{F}_q ^n)$ is the set of all subspace of $\mathbb{F}_q$ of dimension k, and $E=\{ W_1,W_2 \in V | ...

**9**

votes

**1**answer

313 views

### Coherence between different ranking methods of a graph's vertices

Given a (connected) graph $G$ it is natural to want to rank its vertices, with the more "central" vertices ranked higher.
Two natural ways of doing it are:
By the degrees.
By the entries in a ...

**2**

votes

**0**answers

138 views

### If two graphs have same Laplacian spectrums, are they the similar graphs?

If graph A and graph B have exactly the same Laplacian spectrums, can I just say they are same graphs? (only with scaling edge weights and node index reordering) I don't know if there is any explicit ...

**0**

votes

**0**answers

66 views

### Constructing a digraph from its spectrum

This is related to the following question from cs theory stack exchange:
http://cstheory.stackexchange.com/questions/3742/reverse-graph-spectra-problem
So it seems as if given a sequence of real ...

**2**

votes

**0**answers

207 views

### On the existence of Graph Monomorphism

A graph monomorphism is an injective graph homomorphism. Determining existence of Graph monomorphism between graph pairs is computationally hard.
Assume we talk only about classes of undirected ...

**1**

vote

**1**answer

222 views

### When does graph Laplacian have eigenvalue -1?

Consider an undirected graph $G$ with (symmetric) adjacency matrix $A \in \{0,1\}^{n \times n}$ and degree sequence $d = (d_i)$ where $d_i = \sum_{j} A_{ij}$. Assume that every node has degree at ...

**7**

votes

**1**answer

297 views

### normalized laplacian spectrum of trees

Is it known for which class of graphs the normalized laplacian has only simple eigenvalues (i.e., with multiplicity one)? In particular, are there trees (or perhaps a specific class of trees) whose ...

**2**

votes

**1**answer

188 views

### Cospectrality and dimension of graphs

Firstly, I apologize if the question is long. I appreciate any helpful answers and ideas.
In the following all graphs are simple and connected.
Let $G$ be graph with vertex set ...

**2**

votes

**2**answers

263 views

### What is the state of the art on triangle-free strongly regular graphs?

From what I've read I've gathered the following facts:
There are seven known such graphs.
Certain parameter sets are ruled out by the Krein conditions and the absolute bound.
Beyond that, little or ...

**4**

votes

**1**answer

238 views

### How to find or constrain “particularly good” (two-sided) spectral expanders?

I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs.
A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = Î»1 â‰¥ ...

**1**

vote

**2**answers

129 views

### Are trees spectrally determined?

Are trees (connected acyclic graphs) determinable up to isomorphism by their spectra or characteristic polynomials? If not, what other pieces of information may help determine the tree?

**3**

votes

**0**answers

232 views

### A problem on graph theory and complex numbers!

Let ${\mathcal G} = ({\mathcal V},{\mathcal E})$ be a simple connected undirected graph with $n$ vertices. Also let $z_1, \ldots, z_n \in {\mathbb C}$ be complex numbers such that
$$
||z_1||=\ldots = ...

**10**

votes

**0**answers

232 views

### Spectral theory of graph Laplacian besides $\lambda_2$

Most of what I've seen about the spectral theory of the graph Laplacian concentrates on $\lambda_2$, the second-smallest eigenvalue. This eigenvalue contains information regarding the connectivity of ...

**1**

vote

**0**answers

65 views

### Effect of removing a Hamiltonian cycle on the Laplacian spectrum

Notation: $\lambda_{\max}(G)$ is the largest eigenvalue of the Laplacian matrix of the graph $G$ (aka the Laplacian index of $G$).
Now suppose $G$ is a Hamiltonian graph with Hamiltonian cycle $C$.
...

**1**

vote

**0**answers

122 views

### Recovering a partition from spectral properties of the graph Laplacian

Let $G$ be a weighted graph with vertices $V$. Let $W$ be its real-valued, non-negative, $|V|\times|V|$ adjacency/affinity matrix. Let $L = \mathrm{diag}(W\mathbf1)-W$ be the (unnormalized) graph ...

**4**

votes

**1**answer

210 views

### What is the largest possible operator norm of a sparse (0,1)-matrix?

Inspired by this question, I was wondering about the following problem:
Consider all $n\times n$ $(0,1)$-matrices with $k$ ones. Which of these matrices has the largest operator norm? And how does ...

**-1**

votes

**1**answer

218 views

### Upper bound on iterations count for power iteration algorithm

I'm stuck trying to get upper bound on iterations count for power iteration algroithm for finding first eigenvalue of adjacency matrix $A$ given tolerance value. I've tried to figure something out ...

**1**

vote

**2**answers

202 views

### Random walk on the hypercube

Consider the hypercube $Q_4$. I would like to know how to compute the number of steps of a random walk in this graph such that the probability to be at a vertex is a given number $x$. I think I just ...

**11**

votes

**1**answer

262 views

### Variant of an Expander graph: Probability that S random points cast a shadow/projection of size at most S/2 on each face of a cube.

Consider an integer cube of size $\sqrt{k} \times \sqrt{k} \times \sqrt{k}$, where $k$ is an asymptotically large perfect square number. Place k points in this cube at uniformly random locations, ...

**1**

vote

**1**answer

99 views

### Spectrum of composition of graphs( lexicographic product)

I was wondering how to relate the spectra of the composition of two graphs in term of the factors...someone can help me?

**4**

votes

**1**answer

513 views

### How many distinct eigenvalues does a random graph have?

It is well-known that a random graph a.e. has diameter 2. It is also well-known that the number of distinct eigenvalues of a graph is at least the diameter plus one.
But what is known about the ...

**0**

votes

**0**answers

90 views

### Global solution for spectral clustering

I used spectral clustering for directed graphs suggested by Dengyong Zhou paper to partition the graph.I selected the eigen vectors corresponding to k largest eigen values and then I use kmeans or FCM ...

**1**

vote

**2**answers

250 views

### How to identify bridge nodes between nearly connected graph components in partitioned adjacency matrices?

I have adjacency matrices which have nearly connected components. That is partitions with a dense number of edges between nodes in the same group and few edges acting as bridges between these groups. ...

**0**

votes

**1**answer

322 views

### Find edge weights that fit given node weights

Let $G = (V,E)$ be a connected simple graph (unweighted, undirected, no selfloops) on $n$ nodes.
Let $\mathbf{d} := (d_1, d_2, ..., d_n) \in \mathbb{R}_{>0}^n$ be a vector of arbitrary given node ...

**0**

votes

**1**answer

1k views

### Can the first non-zero eigenvalue of a Laplacian matrix with more than 1 zero valued eigenvalue be used to reorder an adjacency matrix?

I have a graph with multiple connected components, and its adjacency matrix. I form the Laplacian matrix (wiki Laplacian matrix), and from the 1K nodes there around ...

**1**

vote

**1**answer

142 views

### The cliques of cospectral graphs

There are some facts that can be found by the spectrum of adjacency matrix of graph.For example, the number of edges and vertices, is bipartite or not, is complete multipartite or not and so on. Can ...

**0**

votes

**2**answers

290 views

### Confused about orbits

I am trying to apply the main theorem of this paper to a certain kind of graph and keep getting confused. The theorem uses $rank(Aut\Gamma)$ which is defined as "the number of $Aut \Gamma$ orbits on ...

**1**

vote

**1**answer

137 views

### The smallest eigenvalue from an equitable partitions

Suppose that $G$ is a connected graph with equitable partition $\pi$. Then the eigenvalues of the divisor multigraph $G / \pi$ are all eigenvalues of $G$. (Perhaps excluding some pathological cases) ...

**2**

votes

**1**answer

365 views

### “Nice” eigenvectors for (square of) adjacency matrix of a bipartite graph?

Let $G$ be a bipartite graph, and let $A$ be its adjacency matrix.
I was wondering in this case whether $A^2$ will have nice eigenvectors that reflect combinatorial structure of the graph. I'd be ...

**2**

votes

**2**answers

353 views

### Extreme Laplacian eigenvalues

For each undirected (and unweighted) graph $G$ we define the Laplacian matrix by $L(G) = D(G)-A(G)$, where $A(G)$ should denote the adjacency matrix and $D(G)$ the diagonal matrix, where $D(G)_{ii}$ ...

**5**

votes

**0**answers

150 views

### When can the Cheeger constant be well-approximated by ``Hamming balls''?

Given a graph G, the Cheeger constant is defined by
$$
\DeclareMathOperator{\Vol}{Vol}
h_G := \min_{S \subseteq V, \Vol S \leq (\Vol G)/2} \frac{|\partial S|}{\Vol S}.
$$
Here, $\Vol S$ is the sum of ...

**1**

vote

**1**answer

140 views

### a variation on the theory of equitable partitions for graphs

Assume you have a graph with an equitable partition with respect to cells $V_1,\ldots,V_n$. Accordingly, you can take the cellwise average value of a function on the node set - in other words, the ...

**5**

votes

**2**answers

249 views

### Number of trees with the same matching number

Let $\sigma(n,m)$ be the number of trees with $n$ vertices $\{ v_1, \dots, v_n \}$ such that the matching number (the size of a maximum matching) is $m$.
I have been trying to compute the value of ...

**5**

votes

**1**answer

362 views

### Repeated Second Eigenvalue of the Adjacency Matrix of a Graph

This question is motivated by a talk I went to earlier today.
Suppose we have a $d$-regular graph $G$ with $n$ vertices, with adjacency matrix $A$.
Let $$\lambda_1\geq \lambda_2 \geq\dots \geq ...

**1**

vote

**1**answer

125 views

### In what probability does cospectra of Cayley graph imply isomorphism of the corresponding group

In what probability does cospectra of adjacent matrix of Cayley graph imply isomorphism of the corresponding group?
Further more,In what probability does cospectra of adjacent matrix imply isomorphism ...