All Questions
67 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
2
answers
198
views
Topology of directed graph $G$ with non-singular adjacency matrix
Given a directed graph $G$ with non-singular adjacency matrix,
Q. Is there a directed
subgraph $H$ in $G$ that can be represented as the union of disjoint cycles such that $H$ contains all nodes of $...
- 4,058
3
votes
1
answer
241
views
Some questions about induced subgraphs of the directed hypercube graph
Let $Q^n$ be the hypercube graph in $n$ dimensions. Hao Huang famously showed that any induced subgraph on more than $2^{n-1}$ must have maximum degree $ \geq \sqrt{n}$. It is also known that this ...
- 129
0
votes
1
answer
82
views
Number of bi-directional (or symmetric edges) [closed]
I am trying to figure out the least number of directed edges that would be bi-directional after constructing a graph with $2k-1$ nodes that are each $k$ in-degree. For example, $2(2)-1=3$ nodes that ...
- 1
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
1
vote
0
answers
50
views
Bounds on the spectral radius of a perturbed directed graph
Suppose $(G_n)$ is a sequence of strongly connected directed graphs (without multiple edges) with $G_n$ having $n$ edges such that the adjacency matrix $A_n$ of $G_n$ is primitive, and let $(G_n’)$ be ...
- 11
3
votes
1
answer
148
views
Spectrum of the adjacency matrix of certain directed graphs
For an undirected graph $G$, its adjacency matrix $A_G$ is symmetric, and by the (consequence of) spectral theorem, each of its Jordan blocks has size $1$. This is not true for a general directed ...
- 161
0
votes
1
answer
116
views
Two fractionally isomorphic graphs but only one having eigenvalue zero
I am looking for two undirected graphs $G$ and $H$ of the same order (i.e., they have the same number of vertices) with adjacency matrices $A_G$ and $A_H$, respectively, such that
$G$ and $H$ are ...
- 493
4
votes
1
answer
90
views
Strongly/distance regular graphs over $\mathbb{Z}_2^n$ with the same parameters
I am wondering if there is a known example of a pair of non-isomorphic graphs $G$ and $H$ that are both Cayley graphs for $\mathbb{Z}_2^n$ (for some $n$) and are both distance regular and have the ...
- 2,339
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
2
votes
1
answer
85
views
Counting Euler circuits through labelled trees where $v_1$ and $v_2$ have distance two
Let $T_n$ be the set of all labelled trees with $n$ vertices. For any $T \in T_n$ let $D(T)$ be the 'doubled tree', where each edge of $T$ is replaced by one directed edge in each direction. $D(T)$ is ...
- 1,295
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
0
votes
0
answers
53
views
Variation in eigenvalues of adjacency matrices of regular graphs
What is known about the range of spectra of regular graphs? That is, I wish to know the largest intervals in which the minimum and maximum eigenvalues of a graph lie. For example, it is known that the ...
- 2,089
4
votes
1
answer
195
views
Explicit constructions of regular graphs with very sparse induced subgraphs
Let $d\ge 3$ be a constant. Is there an explicit construction of an infinite family of $d$-regular graphs such that for $G$ in this family with $n$ vertices, every subgraph $H$ of on at most $\alpha n$...
6
votes
1
answer
746
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
1
vote
0
answers
127
views
Delocalization of eigenvectors of graph Laplacians
Let $(V,E)$ be an undirected, connected graph with $n$ nodes. The graph Laplacian is defined as $L = D - A$, where $D$ is the degree matrix and $A$ is the adjacency matrix. Let $0 = \lambda_1 < \...
- 41
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
0
votes
0
answers
300
views
How is the second smallest eigenvalue of normalized laplacian bounded for random graphs?
It is well known that for any graph G following holds
$\frac{\lambda_2}{2} ≤ \phi(G) ≤ \sqrt{2\lambda_2}$, where $\phi(G)$ is the conductance of the graph and $\lambda_2$ is the second smallest ...
- 1
4
votes
0
answers
162
views
Relation between two conjectures on reconstruction of graphs
In spectral graph theory, there is a conjecture that claims: Almost every graph is determined by its adjacency spectrum ($DS$). This conjecture belongs to professor Willem Haemers.
Also, we have a ...
- 4,784
3
votes
1
answer
134
views
Spectral properties of half-transitive graphs
The half-transitive graphs form a curious class of graphs with some kind of intermediate symmetry that is non-trivial to achieve. More precisely, a graph is half-transitive if its symmetry group is
...
- 13.6k
12
votes
1
answer
726
views
Is there Matrix-Tree theorem for counting the bases of a connected matroid?
The famous Kirchhoff's Matrix-Tree theorem counts the number of spanning trees of a connected graph, that is, the number of bases of its cycle matroid. But it appeals to vertices, that's why I do not ...
- 109k
24
votes
6
answers
2k
views
Factorization of the characteristic polynomial of the adjacency matrix of a graph
Let $G$ be a regular graph of valence $d$ with finitely many vertices, let $A_G$ be its adjacency matrix, and let $$P_G(X)=\det(X-A_G)\in\mathbb{Z}[X]$$ be the adjacency polynomial of $G$, i.e., the ...
- 47.4k
17
votes
1
answer
674
views
Graph embeddings in the projective plane: for the 35 forbidden minors, do we know their Colin de Verdière numbers?
The Graph Minor Theorem of Robertson and Seymour asserts
that any minor-closed graph property is determined by a finite set
of forbidden graph minors. It is a broad generalization e.g. of the ...
- 6,917
3
votes
0
answers
154
views
Chromatic number of regular graphs using spectra
There exist inequalities relating the maximum and minimum eigenvalues of the adjacency matrix of a graph with its chromatic numbers, i.e. the Wilf's and Hoffmann's inequalities, which put together ...
- 2,089
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,432
6
votes
1
answer
263
views
An eigenvalue upper bound for 1-walk-regular graphs
Let $G$ be a graph and suppose that $G$ is 1-walk-regular (or, if you prefer, vertex- and edge-transitive, or distance-regular).
Let $\theta_1>\theta_2>\cdots>\theta_m$ be the distinct ...
- 13.6k
2
votes
0
answers
63
views
Antipodal vertices in spectral graph embeddings
Suppose your are given an antipodal graph $G=(V,E)$, that is, for every vertex $v\in V$ there is a unique maximally distant vertex $v'\in V$.
Under which condistions does the following hold:
If $\...
- 13.6k
0
votes
0
answers
125
views
Lower bounds on the length of circuits, depending on the number of times it crosses itself
I have this problem that I have been stuck on for months, and would like to know if somebody can tell me a way to attack the problem. Let me ask the problem in a simple example below.
Let $G(V,E)$ be ...
- 431
2
votes
0
answers
112
views
Number of components of self-index complementary graphs
Let $G$ be a simple graph. We say this graph is self-index complementary ($SIC$) if $\lambda_1 (G)=\lambda_1 (\overline{G})$, where $\lambda_1(G)$ denotes the index of the adjacency matrix of the ...
- 4,784
0
votes
0
answers
67
views
Singular values and the chromatic number
What relation, if any, is there between the singular values of the adjacency matrix ( or possibly incidence matrix) of a simple graph and its chromatic number. Typically, do we have Hoffmann type, or ...
- 2,089
1
vote
0
answers
184
views
Large bounded degree expanders in the hypercube
Does the $n$ dimensional hypercube graph contain large bounded degree expanders as subgraphs? For example, of exponential size in $n$?
If not, one could relax the problem and allow the maximum ...
- 2,772
7
votes
1
answer
343
views
Can the corollary of the Ihara–Bass formula be extended to $ u^2 = 1 $?
Suppose there is a finite undirected graph $G(V,E)$ having $n$ vertices and $m$ edges.
The non-backtracking matrix $B$ is indexed by $2m$ directed edges and defined as
$$
B(a \to b, c \to d) = \delta_{...
- 171
7
votes
1
answer
358
views
Co-spectral fractional isomorphic graphs with different Laplacian spectrum
I am looking for two undirected graphs $G$ and $H$ of the same order (i.e., they have the same number of vertices) such that $G$ and $H$ are
cospectral (i.e., their adjacency matrices $A_G$ and $A_H$ ...
- 493
6
votes
3
answers
437
views
Eigenvalues of the Laplacian of the directed De Bruijn graph
We will denote by $DB(n,k)$ the directed De Bruijn graph, which is a digraph whose vertices are elements of $\{0,1,\dots,k-1\}^n$, and $\sigma_1\cdots \sigma_n$ is connected to $\tau_1\cdots \tau_{n}$ ...
10
votes
1
answer
359
views
An upper bound for the largest Laplacian eigenvalue of a graph in terms of its diameter
Let $G$ be a simple graph with $n$ vertices and $\lambda$ be the largest eigenvalue of its Laplacian operator $L=D-A$. I have some evidence for the following conjecture:
Conjecture: If G has ...
- 4,484
9
votes
3
answers
356
views
Spectrum of orthogonality graph (2)
The orthogonality graph, $\Omega(n)$, has vertex set the set of $\pm 1$ vectors of length $n$, with orthogonal vectors being adjacent.
I am only interested when $4|n$, since otherwise $\Omega(n)$ is ...
- 421
5
votes
0
answers
397
views
spectrum of orthogonality graphs
The orthogonality graph $\Omega(n)$ with $2^n$ vertices is the graph with vertex set $\{-1,+1\}^n$, with two vertices being adjacent if and only if they are orthogonal (as vectors in the standard ...
- 421
1
vote
0
answers
51
views
Relation between nullity of components to its parent graph
Let $G$ be an undirected graph and the corresponding adjacency matrix be $A$. Let $v$ be a cut-vertex of $G$. Let $G_1, G_2,\dots, G_k$ are the connected components of the induced graph $G-v$ ( the ...
- 640
10
votes
0
answers
225
views
Cospectral mate of rhombic dodecahedron
I am wondering if the following pair of cospectral graphs was previously known.
The rhombic dodecahedron graph looks like this (graph6 string: 'M?????rrAiTOd_YO?'):
As far as I know, it was previously ...
- 2,339
8
votes
3
answers
498
views
Where does $2\sqrt{d-1}$ come from in Ramanujan graphs?
Ramanujan graphs are the best spectral expanders: $\lambda_2 \le 2\sqrt{d-1}$. I'm looking for some intuition for this value $2\sqrt{d-1}$.
Friedman showed that every random $d$-regular graph ...
- 1,161
2
votes
1
answer
189
views
Connection between graph spectra and graph homomorphisms [closed]
Since there are many properties of graph which can be expressed in terms of both existence of graph homomorphisms and graph spectra I expect there are some papers exploring this connection between ...
user92031
7
votes
1
answer
312
views
Does an expander remain an expander after removing few vertices and edges?
Consider a sequence of expander graphs ($G_n$); say $G_n$ has $n$ vertices.
Remove $o(n)$ vertices (and the edges emanating from these vertices) and cut $o(n)$ edges. Call $G'_n$ the largest connected ...
- 73
3
votes
1
answer
277
views
Spectra of undirected $d$-regular graphs
Let $G$ be a undirected $d$-regular graph, that is, a graph whose all vertices have the same degree $d$. It is known that the eigenvalues $\sigma_i$, $i=1,\cdots,n$, of the adjacency matrix are real ...
- 33
6
votes
1
answer
583
views
Eigenvalue inequality for regular graphs
I recently proved an inequality relating some of the eigenvalues of a regular graph with each other, and I was wondering if it is already known. I was unable to find it online, and a quick skim ...
- 2,339
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
1
vote
0
answers
232
views
Lp norm estimates for the inverse of the Laplacian on a graph
I am looking at a finite connected graph and I would like to know what is the best [i.e. largest] constant $\lambda_p$ in
$$
\sum_x f(x) =0 \implies \| \Delta^{-1} f\|_{\ell^p} \leq \lambda_p^{-1} \|...
- 4,432
1
vote
0
answers
315
views
When does the normalized graph Laplacian have eigenvalue 1?
Let $G= (V,E)$ be a finite, undirected and unweighted graph with $V = \{v_1,\ldots, v_n\}$. Denote by $d_i$ the degree of $v_i$, i.e. the number of vertices that are adjacent to $v_i$. Let $A$ be the ...
- 119
-2
votes
1
answer
639
views
About structure of the set of perfect matchings of $K_{n,n}$
Are there any special properties known about the set of perfect matchings of $K_{n,n}$? Like any global structure of this set? Some natural way to partition it? Like is there some algebraic structure ...
- 1,893
13
votes
3
answers
4k
views
What is a "Ramanujan Graph"?
I noticed an apparent conflict in the definition in literature about what is a "Ramanujan graph, which I was wondering if someone could kindly clarify.
(1)
The Hoory-Linial-Wigderson review on ...
- 1,893
5
votes
0
answers
267
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 ...
- 3,612