اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the spectral moment of graphs with $k$ cut edges
230
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $A(G)$ be the adjacency matrix of a graph $G$ with $lambda_{1}(G)$, $lambda_{2}(G)$, ..., $lambda_{n}(G)$ being its eigenvalues in non-increasing order. Call the number $S_k(G):=sum_{i=1}^{n}lambda_{i}^k(G) (k=0,1,...,n-1)$ the $k$th spectral moment of $G$. Let $S(G)=(S_0(G),S_1(G),...,S_{n-1}(G))$ be the sequence of spectral moments of $G$. For two graphs $G_1$ and $G_2$, we have $G_1prec_sG_2$ if $S_i(G_1)=S_i(G_2) (i=0,1,...,k-1)$ and $S_k(G_1)<S_k(G_2)$ for some $kin {1,2,...,n-1}$. Denote by $mathscr{G}_n^k$ the set of connected $n$-vertex graphs with $k$ cut edges. In this paper, we determine the first, the second, the last and the second last graphs, in an $S$-order, among $mathscr{G}_n^k$, respectively.
قيم البحث
اقرأ أيضاً
We study $2k$-factors in $(2r+1)$-regular graphs. Hanson, Loten, and Toft proved that every $(2r+1)$-regular graph with at most $2r$ cut-edges has a $2$-factor. We generalize their result by proving for $kle(2r+1)/3$ that every $(2r+1)$-regular graph
with at most $2r-3(k-1)$ cut-edges has a $2k$-factor. Both the restriction on $k$ and the restriction on the number of cut-edges are sharp. We characterize the graphs that have exactly $2r-3(k-1)+1$ cut-edges but no $2k$-factor. For $k>(2r+1)/3$, there are graphs without cut-edges that have no $2k$-factor, as studied by Bollobas, Saito, and Wormald.
Let $mathcal{G}$ be an undirected graph with adjacency matrix $A$ and spectral radius $rho$. Let $w_k, phi_k$ and $phi_k^{(i)}$ be, respectively, the number walks of length $k$, closed walks of length $k$ and closed walks starting and ending at verte
x $i$ after $k$ steps. In this paper, we propose a measure-theoretic framework which allows us to relate walks in a graph with its spectral properties. In particular, we show that $w_k, phi_k$ and $phi_k^{(i)}$ can be interpreted as the moments of three different measures, all of them supported on the spectrum of $A$. Building on this interpretation, we leverage results from the classical moment problem to formulate a hierarchy of new lower and upper bounds on $rho$, as well as provide alternative proofs to several well-known bounds in the literature.
Let $phi_H^r(n)$ be the smallest integer such that, for all $r$-graphs $G$ on $n$ vertices, the edge set $E(G)$ can be partitioned into at most $phi_H^r(n)$ parts, of which every part either is a single edge or forms an $r$-graph isomorphic to $H$. T
he function $phi^2_H(n)$ has been well studied in literature, but for the case $rge 3$, the problem that determining the value of $phi_H^r(n)$ is widely open. Sousa (2010) gave an asymptotic value of $phi_H^r(n)$ when $H$ is an $r$-graph with exactly 2 edges, and determined the exact value of $phi_H^r(n)$ in some special cases. In this paper, we first give the exact value of $phi_H^r(n)$ when $H$ is an $r$-graph with exactly 2 edges, which improves Sousas result. Second we determine the exact value of $phi_H^r(n)$ when $H$ is an $r$-graph consisting of exactly $k$ independent edges.
The Ising antiferromagnet is an important statistical physics model with close connections to the {sc Max Cut} problem. Combining spatial mixing arguments with the method of moments and the interpolation method, we pinpoint the replica symmetry break
ing phase transition predicted by physicists. Additionally, we rigorously establish upper bounds on the {sc Max Cut} of random regular graphs predicted by Zdeborova and Boettcher [Journal of Statistical Mechanics 2010]. As an application we prove that the information-theoretic threshold of the disassortative stochastic block model on random regular graphs coincides with the Kesten-Stigum bound.
Let $G$ be a simple graph with vertex set $V(G) = {v_1 ,v_2 ,cdots ,v_n}$. The Harary matrix $RD(G)$ of $G$, which is initially called the reciprocal distance matrix, is an $n times n$ matrix whose $(i,j)$-entry is equal to $frac{1}{d_{ij}}$ if $i ot
=j$ and $0$ otherwise, where $d_{ij}$ is the distance of $v_i$ and $v_j$ in $G$. In this paper, we characterize graphs with maximum spectral radius of Harary matrix in three classes of simple connected graphs with $n$ vertices: graphs with fixed matching number, bipartite graphs with fixed matching number, and graphs with given number of cut edges, respectively.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
