Source author record

Ebrahim Ghorbani

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

13works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Gap sets for the spectra of regular graphs with minimum spectral gap

Following recent work by Kollár and Sarnak, we study gaps in the spectra of large connected cubic and quartic graphs with minimum spectral gap. We focus on two sequences of graphs, denoted $Δ_n$ and $Γ_n$ which are more `symmetric' compared to the other graphs in these two families, respectively. We prove that $(1,\sqrt{5}]$ is a gap interval for $Δ_n$ , and $[(-1+\sqrt{17})/2,3]$ is a gap interval for $Γ_n$ . We conjecture that these two are indeed maximal gap intervals. As a by-product, we show that the eigenvalues of $Δ_n$ lying in the interval $[-3,-\sqrt{5}]$ (in particular, its minimum eigenvalue) converge to $(1-\sqrt{33})/2$ and the eigenvalues of $Γ_n$ lying in the interval $[-4,-(1+\sqrt{17})/2]$ (and in particular, its minimum eigenvalue) converge to $1-\sqrt{13}$ as $n$ tends to infinity. The proofs of the above results heavily depend on the following property which can be of independent interest: with few exceptions, all the eigenvalues of connected cubic and quartic graphs with minimum spectral gap are simple.

preprint2022arXiv

Quartic Graphs with Minimum Spectral Gap

Aldous and Fill conjectured that the maximum relaxation time for the random walk on a connected regular graph with $n$ vertices is $(1+o(1)) \frac{3n^2}{2π^2}$ . This conjecture can be rephrased in terms of the spectral gap as follows: the spectral gap (algebraic connectivity) of a connected $k$ -regular graph on $n$ vertices is at least $(1+o(1))\frac{2kπ^2}{3n^2}$ , and the bound is attained for at least one value of $k$ . We determine the structure of connected quartic graphs on $n$ vertices with minimum spectral gap which enable us to show that the minimum spectral gap of connected quartic graphs on $n$ vertices is $(1+o(1))\frac{4π^2}{n^2}$ . From this result, the Aldous--Fill conjecture follows for $k=4$ .

preprint2020arXiv

Hamiltonicity of a coprime graph

The $k$ -coprime graph of order $n$ is the graph with vertex set $\{k, k+1, \ldots, k+n-1\}$ in which two vertices are adjacent if and only if they are coprime. We characterize Hamiltonian $k$ -coprime graphs. As a particular case, two conjectures by Tout, Dabboucy, Howalla (1982) and by Schroeder (2019) on prime labeling of $2$ -regular graphs follow. A prime labeling of a graph with $n$ vertices is a labeling of its vertices with distinct integers from $\{1, 2,\ldots , n\}$ in such a way that the labels of any two adjacent vertices are relatively prime.

preprint2020arXiv

On sign-symmetric signed graphs

A signed graph is said to be sign-symmetric if it is switching isomorphic to its negation. Bipartite signed graphs are trivially sign-symmetric. We give new constructions of non-bipartite sign-symmetric signed graphs. Sign-symmetric signed graphs have a symmetric spectrum but not the other way around. We present constructions of signed graphs with symmetric spectra which are not sign-symmetric. This, in particular answers a problem posed by Belardo, Cioabă, Koolen, and Wang (2018).

preprint2016arXiv

Nontrivial nuciferous graphs exist

A nuciferous graph is a simple graph with a non-singular $0$ - $1$ adjacency matrix $A$ such that all the diagonal entries of $A^{-1}$ are zero and all the off-diagonal entries of $A^{-1}$ are non-zero. Sciriha et al. conjectured that except $K_2$ , no nuciferous graph exists. We disprove this conjecture. Moreover, we conjecture that there infinitely many nuciferous Cayley graphs.

preprint2016arXiv

Proof of a conjecture on `plateaux' phenomenon of graph Laplacian eigenvalues

Let $G$ be a simple graph. A pendant path of $G$ is a path such that one of its end vertices has degree $1$ , the other end has degree $\ge3$ , and all the internal vertices have degree $2$ . Let $p_k(G)$ be the number of pendant paths of length $k$ of $G$ , and $q_k(G)$ be the number of vertices with degree $\ge3$ which are an end vertex of some pendant paths of length $k$ . Motivated by the problem of characterizing dendritic trees, N. Saito and E. Woei conjectured that any graph $G$ has some Laplacian eigenvalue with multiplicity at least $p_k(G)-q_k(G)$ . We prove a more general result for both Laplacian and signless Laplacian eigenvalues from which the conjecture follows.

preprint2014arXiv

Spanning trees and even integer eigenvalues of graphs

For a graph $G$ , let $L(G)$ and $Q(G)$ be the Laplacian and signless Laplacian matrices of $G$ , respectively, and $τ(G)$ be the number of spanning trees of $G$ . We prove that if $G$ has an odd number of vertices and $τ(G)$ is not divisible by $4$ , then (i) $L(G)$ has no even integer eigenvalue, (ii) $Q(G)$ has no integer eigenvalue $λ\equiv2\pmod4$ , and (iii) $Q(G)$ has at most one eigenvalue $λ\equiv0\pmod4$ and such an eigenvalue is simple. As a consequence, we extend previous results by Gutman and Sciriha and by Bapat on the nullity of adjacency matrices of the line graphs. We also show that if $τ(G)=2^ts$ with $s$ odd, then the multiplicity of any even integer eigenvalue of $Q(G)$ is at most $t+1$ . Among other things, we prove that if $L(G)$ or $Q(G)$ has an even integer eigenvalue of multiplicity at least $2$ , then $τ(G)$ is divisible by $4$ . As a very special case of this result, a conjecture by Zhou et al. [On the nullity of connected graphs with least eigenvalue at least $-2$ , Appl. Anal. Discrete Math. 7 (2013), 250--261] on the nullity of adjacency matrices of the line graphs of unicyclic graphs follows.

preprint2013arXiv

Cyclic decomposition of k-permutations and eigenvalues of the arrangement graphs

The (n,k)-arrangement graph A(n,k) is a graph with all the k-permutations of an n-element set as vertices where two k-permutations are adjacent if they agree in exactly k-1 positions. We introduce a cyclic decomposition for k-permutations and show that this gives rise to a very fine equitable partition of A(n,k). This equitable partition can be employed to compute the complete set of eigenvalues (of the adjacency matrix) of A(n,k). Consequently, we determine the eigenvalues of A(n,k) for small values of k. Finally, we show that any eigenvalue of the Johnson graph J(n,k) is an eigenvalue of A(n,k) and that -k is the smallest eigenvalue of A(n,k) with multiplicity O(n^k) for fixed k.

preprint2013arXiv

Inverses of triangular matrices and bipartite graphs

To a given nonsingular triangular matrix A with entries from a ring, we associate a weighted bipartite graph G(A) and give a combinatorial description of the inverse of A by employing paths in G(A). Under a certain condition, nonsingular triangular matrices A such that A and A^{-1} have the same zero-nonzero pattern are characterized. A combinatorial construction is given to construct outer inverses of the adjacency matrix of a weighted tree.

preprint2013arXiv

On eigenvalues of Seidel matrices and Haemers' conjecture

For a graph $G$ , let $S(G)$ be the Seidel matrix of $G$ and $\te_1(G),...,\te_n(G)$ be the eigenvalues of $S(G)$ . The Seidel energy of $G$ is defined as $|\te_1(G)|+...+|\te_n(G)|$. Willem Haemers conjectured that the Seidel energy of any graph with $n$ vertices is at least $2n-2$ , the Seidel energy of the complete graph with $n$ vertices. Motivated by this conjecture, we prove that for any $\al$ with $0<\al<2$, $|\te_1(G)|^\al+...+|\te_n(G)|^\al\g (n-1)^\al+n-1$ if and only if $|{\rm det} S(G)|\g n-1$. This, in particular, implies the Haemers' conjecture for all graphs $G$ with $|{\rm det} S(G)|\g n-1$.

preprint2013arXiv

On the eigenvalues of certain Cayley graphs and arrangement graphs

In this paper, we show that the eigenvalues of certain classes of Cayley graphs are integers. The (n,k,r)-arrangement graph A(n,k,r) is a graph with all the k-permutations of an n-element set as vertices where two k-permutations are adjacent if they differ in exactly r positions. We establish a relation between the eigenvalues of the arrangement graphs and the eigenvalues of certain Cayley graphs. As a result, the conjecture on integrality of eigenvalues of A(n,k,1) follows.

preprint2012arXiv

Graphs with few matching roots

We determine all graphs whose matching polynomials have at most five distinct zeros. As a consequence, we find new families of graphs which are determined by their matching polynomial.

preprint2011arXiv

Bipartite graphs with five eigenvalues and pseudo designs

A pseudo $(v,\, k,\, \la)$-design is a pair $(X, {\cal B})$ where $X$ is a $v$ -set and ${\cal B}=\{B_1,...,B_{v-1}\}$ is a collection of $k$ -subsets (blocks) of $X$ such that each two distinct $B_i, B_j$ intersect in $\la$ elements; and $0\le\la <k \le v-1$. We use the notion of pseudo designs to characterize graphs of order $n$ whose (adjacency) spectrum contains a zero and $\pmθ$ with multiplicity $(n-3)/2$ where $0<θ\le\sqrt{2}$ . Meanwhile, partial results confirming a conjecture of O. Marrero on characterization of pseudo $(v,\, k,\, \la)$-designs are obtained.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Ebrahim Ghorbani

Research overview

Is this your work?

13 publications

Gap sets for the spectra of regular graphs with minimum spectral gap

Quartic Graphs with Minimum Spectral Gap

Hamiltonicity of a coprime graph

On sign-symmetric signed graphs

Nontrivial nuciferous graphs exist

Proof of a conjecture on `plateaux' phenomenon of graph Laplacian eigenvalues

Spanning trees and even integer eigenvalues of graphs

Cyclic decomposition of k-permutations and eigenvalues of the arrangement graphs

Inverses of triangular matrices and bipartite graphs

On eigenvalues of Seidel matrices and Haemers' conjecture

On the eigenvalues of certain Cayley graphs and arrangement graphs

Graphs with few matching roots

Bipartite graphs with five eigenvalues and pseudo designs

See the researcher in context

Building this map preview