All Questions
11 questions
3
votes
0
answers
61
views
Is this bipartite equivalent of 1-walk-regular graphs known?
A graph $G$ is 1-walk-regular if
for each vertex $v$ the number of closed walks of length $\ell$ starting (and ending) at $v$ depends only on $\ell$ but not on $v$.
for each edge $vw$ the number of ...
- 13.6k
1
vote
1
answer
177
views
Spectral characterization of complete or complete bipartite graphs
The Lemma 6 in this paper mention the following spectral characterization of complete or complete bipartite graphs:
Let $G$ be a connected graph with $\ge 2$ vertices. Then $\lambda_2=...=\lambda_{n-...
- 243
0
votes
0
answers
55
views
Comparing spectral radius of two graphs using the entry of Perron vector
Suppose we have a graph $G$.
Let $A$ be the adjacency matrix of $G$ and $x$ be the corresponding Perron vector.
Let $x = (x_1,x_2,\cdots,x_n)^t$, where $x_i$ corresponds to the vertex $i \in V(G)$.
We ...
- 199
0
votes
0
answers
120
views
Does an extension of the B.E.S.T. theorem for multiple Eulerian circuits exist?
Given a directed multigraph $G=(V,E)$ (multiple edges and loops are permitted) the number of distinct Eulerian circuits for $G$ can be calculated with the B.E.S.T. theorem. Does a similar theory for ...
- 1,295
4
votes
0
answers
176
views
Can resolution of the Kadison-Singer Problem provide progress on the Komlos Conjecture?
This is not a concrete question, just some thoughts.
The Komlos Conjecture is as follows-
There exists an absolute constant $C>0$, such that the following holds:
For all $d$ and any set of vectors ...
- 150
6
votes
1
answer
744
views
Relationship between spectral gaps of adjacency and Laplacian matrices of graphs
Let $G$ be an undirected simple graph on $n$ vertices, with self-loops allowed, and with arbitrary positive edge weights $w_{u,v}$ (which is $0$ if there is no edge between $u$ and $v$).
Let $A$ be ...
- 150
3
votes
1
answer
143
views
Reference request: Spectrum of intersection matrices
Let $P(A)$ be the set of all non-empty proper subsets of a finite set $A$. Let $M$ be a matrix indexed by the set in $P(A)$ whose $ij$ the entry is $1$ if the associated sets are disjoint and $0$ ...
- 1,269
34
votes
1
answer
789
views
Which graphs on $n$ vertices have the largest determinant?
This is a question that seems like it should have been studied before, but for some reason I cannot find much at all about it, and so I am asking for any pointers / references etc.
The determinant of ...
- 12.7k
1
vote
0
answers
121
views
Cheeger constant of truncated hypercube
Look at the $d$-dimensional hypercube and truncate it. This means one replaces each vertex by a cycle (of length $d$) in such a way the the new graph is 3-regular.
Question 1: What is the asymptotic ...
- 4,422
9
votes
1
answer
261
views
Expansion in strongly regular graphs
Have you seen the following statement proven anywhere?
Let $G$ be a strongly regular graph with parameters $(n,k,\lambda,\mu)$ with $\lambda,\mu>0$. Then there is no set $A$ of at least $n/4$ ...
- 93
17
votes
8
answers
10k
views
The first eigenvalue of a graph - what does it reflect?
A big-picture question: what "physical properties" of a graph, and in particular of a bipartite graph, are encoded by its largest eigenvalue? If $U$ and $V$ are the partite sets of the graph, with the ...
- 23k