اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدSpectral Radius and Degree Sequence of a Graph
197
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let G be a simple connected graph of order n with degree sequence d_1, d_2, ..., d_n in non-increasing order. The spectral radius rho(G) of G is the largest eigenvalue of its adjacency matrix. For each positive integer L at most n, we give a sharp upper bound for rho(G) by a function of d_1, d_2, ..., d_L, which generalizes a series of previous results.
قيم البحث
اقرأ أيضاً
This paper presents sufficient conditions for Hamiltonian paths and cycles in graphs. Letting $lambdaleft( Gright) $ denote the spectral radius of the adjacency matrix of a graph $G,$ the main results of the paper are: (1) Let $kgeq1,$ $ngeq k^{3}/
2+k+4,$ and let $G$ be a graph of order $n$, with minimum degree $deltaleft( Gright) geq k.$ If [ lambdaleft( Gright) geq n-k-1, ] then $G$ has a Hamiltonian cycle, unless $G=K_{1}vee(K_{n-k-1}+K_{k})$ or $G=K_{k}vee(K_{n-2k}+overline{K}_{k})$. (2) Let $kgeq1,$ $ngeq k^{3}/2+k^{2}/2+k+5,$ and let $G$ be a graph of order $n$, with minimum degree $deltaleft( Gright) geq k.$ If [ lambdaleft( Gright) geq n-k-2, ] then $G$ has a Hamiltonian path, unless $G=K_{k}vee(K_{n-2k-1}+overline {K}_{k+1})$ or $G=K_{n-k-1}+K_{k+1}$ In addition, it is shown that in the above statements, the bounds on $n$ are tight within an additive term not exceeding $2$.
The deck of a graph $G$ is the multiset of cards ${G-v:vin V(G)}$. Myrvold (1992) showed that the degree sequence of a graph on $ngeq7$ vertices can be reconstructed from any deck missing one card. We prove that the degree sequence of a graph with av
erage degree $d$ can reconstructed from any deck missing $O(n/d^3)$ cards. In particular, in the case of graphs that can be embedded on a fixed surface (e.g. planar graphs), the degree sequence can be reconstructed even when a linear number of the cards are missing.
We obtain new bounds for the Laplacian spectral radius of a signed graph. Most of these new bounds have a dependence on edge sign, unlike previously known bounds, which only depend on the underlying structure of the graph. We then use some of these b
ounds to obtain new bounds for the Laplacian and signless Laplacian spectral radius of an unsigned graph by signing the edges all positive and all negative, respectively.
We prove an asymptotic formula for the number of orientations with given out-degree (score) sequence for a graph $G$. The graph $G$ is assumed to have average degrees at least $n^{1/3 + varepsilon}$ for some $varepsilon > 0$, and to have strong mixin
g properties, while the maximum imbalance (out-degree minus in-degree) of the orientation should be not too large. Our enumeration results have applications to the study of subdigraph occurrences in random orientations with given imbalance sequence. As one step of our calculation, we obtain new bounds for the maximum likelihood estimators for the Bradley-Terry model of paired comparisons.
Let k, p, q be positive integers with k < p < q+1. We prove that the maximum spectral radius of a simple bipartite graph obtained from the complete bipartite graph Kp,q of bipartition orders p and q by deleting k edges is attained when the deleting e
dges are all incident on a common vertex which is located in the partite set of order q. Our method is based on new sharp upper bounds on the spectral radius of bipartite graphs in terms of their degree sequences.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
