اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn some papers of Nikiforov
54
0
0.0
(
0
)
تأليف
Bo Ning
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The well known Mantels Theorem states that a graph on $n$ vertices and $m$ edges contains a triangle if $m>frac{n^2}{4}$. Nosal proved that every graph on $m$ edges contains a triangle if the spectral radius $lambda_1>sqrt{m}$, which is a spectral analog of Mantels Theorem. Furthermore, by using Motzkin-Straus Inequality, Nikiforov sharped Nosals result and characterized the extremal graphs when the equality holds. Our first contribution in this note is to give two new proofs of the spectral concise Mantels Theorem due to Nikiforov (without help of Motzkin-Straus Inequality). Nikiforov also obtained some results concerning the existence of consecutive cycles and spectral radius. Second, we prove a theorem concerning the existence of consecutive even cycles and spectral radius, which slightly improves a result of Nikiforov. At last, we focus on spectral radius inequalities. Hong proved his famous bound for spectral radius. Later, Hong, Shu and Fang generalized Hongs bound to connected graphs with given minimum degree. By using quite different technique, Nikiforov proved Hong et al.s bound for general graphs independently. In this note, we prove a new spectral inequality by applying the technique of Nikiforov. Our result extends Stanleys spectral inequality.
قيم البحث
اقرأ أيضاً
In 1965, Motzkin and Straus [5] provided a new proof of Turans theorem based on a continuous characterization of the clique number of a graph using the Lagrangian of a graph. This new proof aroused interests in the study of Lagrangians of r-uniform g
raphs. The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. Sidorenko and Frankl-Furedi applied Lagrangians of hypergraphs in finding Turan densities of hypergraphs. Frankl and Rodl applied it in disproving Erdos jumping constant conjecture. In most applications, we need an upper bound for the Lagrangian of a hypergraph. Frankl and Furedi conjectured that the r-uniform graph with m edges formed by taking the first m sets in the colex ordering of $N^(r)$ has the largest Lagrangian of all r-uniform graphs with m edges. Talbot in [14] provided some evidences for Frankl and Furedis conjecture. In this paper, we prove that the r-uniform graph with m edges formed by taking the first m sets in the colex ordering of $N^(r)$ has the largest Lagrangian of all r-uniform graphs on t vertices with m edges when ${t choose r}-3$ or ${t choose r}-4$. As an implication, we also prove that Frankl and Furedis conjecture holds for 3-uniform graphs with ${t choose 3}-3$ or ${t choose 3}-4$ edges.
We exhibit a particular free subarrangement of a certain restriction of the Weyl arrangement of type $E_7$ and use it to give an affirmative answer to a recent conjecture by T.~Abe on the nature of additionally free and stair-free arrangements.
In this paper, firstly we show that the entropy constants of the number of independent sets on certain plane lattices are the same as the entropy constants of the corresponding cylindrical and toroidal lattices. Secondly, we consider three more compl
ex lattices which can not be handled by a single transfer matrix as in the plane quadratic lattice case. By introducing the concept of transfer multiplicity, we obtain the lower and upper bounds of the entropy constants of crossed quadratic lattice, generalized aztec diamond lattice and 8-8-4 lattice.
Given a proper edge coloring $varphi$ of a graph $G$, we define the palette $S_{G}(v,varphi)$ of a vertex $v in V(G)$ as the set of all colors appearing on edges incident with $v$. The palette index $check s(G)$ of $G$ is the minimum number of distin
ct palettes occurring in a proper edge coloring of $G$. In this paper we give various upper and lower bounds on the palette index of $G$ in terms of the vertex degrees of $G$, particularly for the case when $G$ is a bipartite graph with small vertex degrees. Some of our results concern $(a,b)$-biregular graphs; that is, bipartite graphs where all vertices in one part have degree $a$ and all vertices in the other part have degree $b$. We conjecture that if $G$ is $(a,b)$-biregular, then $check{s}(G)leq 1+max{a,b}$, and we prove that this conjecture holds for several families of $(a,b)$-biregular graphs. Additionally, we characterize the graphs whose palette index equals the number of vertices.
Visibility representation of digraphs was introduced by Axenovich, Beveridge, Hutch-inson, and West (emph{SIAM J. Discrete Math.} {bf 27}(3) (2013) 1429--1449) as a natural generalization of $t$-bar visibility representation of undirected graphs. A {
it $t$-bar visibility representation} of a digraph $G$ assigns each vertex at most $t$ horizontal bars in the plane so that there is an arc $xy$ in the digraph if and only if some bar for $x$ sees some bar for $y$ above it along an unblocked vertical strip with positive width. The {it visibility number} $b(G)$ is the least $t$ such that $G$ has a $t$-bar visibility representation. In this paper, we solve several problems about $b(G)$ posed by Axenovich et al. and prove that determining whether the bar visibility number of a digraph is $2$ is NP-complete.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
