ترغب بنشر مسار تعليمي؟ اضغط هنا

Constraints on Brouwers Laplacian Spectrum Conjecture

207   0   0.0 ( 0 )
 نشر من قبل Joshua N. Cooper
 تاريخ النشر 2020
  مجال البحث
والبحث باللغة English
 تأليف Joshua N. Cooper




اسأل ChatGPT حول البحث

Brouwers Conjecture states that, for any graph $G$, the sum of the $k$ largest (combinatorial) Laplacian eigenvalues of $G$ is at most $|E(G)| + binom{k+1}{2}$, $1 leq k leq n$. We present several interrelated results establishing Brouwers conjecture $text{BC}_k(G)$ for a wide range of graphs $G$ and parameters $k$. In particular, we show that (1) $text{BC}_k(G)$ is true for low-arboricity graphs, and in particular for planar $G$ when $k geq 11$; (2) $text{BC}_k(G)$ is true whenever the variance of the degree sequence is not very high, generalizing previous results for $G$ regular or random; (3) $text{BC}_k(G)$ is true if $G$ belongs to a hereditarily spectrally-bounded class and $k$ is sufficiently large as a function of $k$, in particular $k geq sqrt{32n}$ for bipartite graphs; (4) $text{BC}_k(G)$ holds unless $G$ has edge-edit distance $< k sqrt{2n} = O(n^{3/2})$ from a split graph; (5) no $G$ violates the conjectured upper bound by more than $O(n^{5/4})$, and bipartite $G$ by no more than $O(n)$; and (6) $text{BC}_k(G)$ holds for all $k$ outside an interval of length $O(n^{3/4})$. Furthermore, we present a surprising negative result: asymptotically almost surely, a uniform random signed complete graph violates the conjectured bound by $Omega(n)$.



قيم البحث

اقرأ أيضاً

The spectrum of the normalized graph Laplacian yields a very comprehensive set of invariants of a graph. In order to understand the information contained in those invariants better, we systematically investigate the behavior of this spectrum under lo cal and global operations like motif doubling, graph joining or splitting. The eigenvalue 1 plays a particular role, and we therefore emphasize those constructions that change its multiplicity in a controlled manner, like the iterated duplication of nodes.
A connected graph $G$ is a cactus if any two of its cycles have at most one common vertex. Let $ell_n^m$ be the set of cacti on $n$ vertices with matching number $m.$ S.C. Li and M.J. Zhang determined the unique graph with the maximum signless Laplac ian spectral radius among all cacti in $ell_n^m$ with $n=2m$. In this paper, we characterize the case $ngeq 2m+1$. This confirms the conjecture of Li and Zhang(S.C. Li, M.J. Zhang, On the signless Laplacian index of cacti with a given number of pendant vetices, Linear Algebra Appl. 436, 2012, 4400--4411). Further, we characterize the unique graph with the maximum signless Laplacian spectral radius among all cacti on $n$ vertices.
95 - Pinchen Xie , Zhongzhi Zhang , 2015
Determining and analyzing the spectra of graphs is an important and exciting research topic in theoretical computer science. The eigenvalues of the normalized Laplacian of a graph provide information on its structural properties and also on some rele vant dynamical aspects, in particular those related to random walks. In this paper, we give the spectra of the normalized Laplacian of iterated subdivisions of simple connected graphs. As an example of application of these results we find the exact values of their multiplicative degree-Kirchhoff index, Kemenys constant and number of spanning trees.
71 - Yuyang Xu , Jianfeng Yao 2019
For dendrite graphs from biological experiments on mouses retinal ganglion cells, a paper by Nakatsukasa, Saito and Woei reveals a mysterious phase transition phenomenon in the spectra of the corresponding graph Laplacian matrices. While the bulk of the spectrum can be well understood by structures resembling starlike trees, mysteries about the spikes, that is, isolated eigenvalues outside the bulk spectrum, remain unexplained. In this paper, we bring new insights on these mysteries by considering a class of uniform trees. Exact relationships between the number of such spikes and the number of T-junctions are analyzed in function of the number of vertices separating the T-junctions. Using these theoretic results, predictions are proposed for the number of spikes observed in real-life dendrite graphs. Interestingly enough, these predictions match well the observed numbers of spikes, thus confirm the practical meaningness of our theoretical results.
Let $G$ be a $k$-connected graph on $n$ vertices. Hippchens Conjecture states that two longest paths in $G$ share at least $k$ vertices. Gutierrez recently proved the conjecture when $kleq 4$ or $kgeq frac{n-2}{3}$. We improve upon both results; name ly, we show that two longest paths in $G$ share at least $k$ vertices when $k=5$ or $kgeq frac{n+2}{5}$. This completely resolves two conjectures of Gutierrez in the affirmative.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا