首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
《Discrete Mathematics》2022,345(1):112669
In this paper, we consider two kinds of spectral extremal questions. The first asks which graph attains the maximum Q-index over all graphs of order n and size m=n+k? The second asks which graph attains the maximum Q-index over all (p,q)-bipartite graphs with m=p+q+k edges? We solve the first question for 4kn?3, and the second question for ?p?qkp?q. The maximum Q-index on connected (p,q)-bipartite graphs is also determined for ?1kp?2.  相似文献   

3.
《Discrete Mathematics》2022,345(5):112786
Let G be a connected graph with n(G) vertices and e(G) edges. The nullity of G, denoted by η(G), is the multiplicity of eigenvalue zero of the adjacency matrix of G. Ma, Wong and Tian (2016) proved that η(G)2c(G)+p(G)?1 unless G is a cycle of order a multiple of 4, where c(G)=e(G)?n(G)+1 is the elementary cyclic number of G and p(G) is the number of leaves of G. Recently, Chang, Chang and Zheng (2020) characterized the leaf-free graphs with nullity 2c(G)?1, thus leaving the problem to characterize connected graphs G with nullity 2c(G)+p(G)?1 when p(G)0. In this paper, we solve this problem completely.  相似文献   

4.
5.
6.
《Discrete Mathematics》2022,345(4):112774
Chvátal and Erdös (1972) [5] proved that, for a k-connected graph G, if the stability number α(G)k?s, then G is Hamilton-connected (s=1) or Hamiltonian (s=0) or traceable (s=?1). Motivated by the result, we focus on tight sufficient spectral conditions for k-connected graphs to possess Hamiltonian s-properties. We say that a graph possesses Hamiltonian s-properties, which means that the graph is Hamilton-connected if s=1, Hamiltonian if s=0, and traceable if s=?1.For a real number a0, and for a k-connected graph G with order n, degree diagonal matrix D(G) and adjacency matrix A(G), we have identified best possible upper bounds for the spectral radius λ1(aD(Γ)+A(Γ)), where Γ is either G or the complement of G, to warrant that G possesses Hamiltonian s-properties. Sufficient conditions for a graph G to possess Hamiltonian s-properties in terms of upper bounds for the Laplacian spectral radius as well as lower bounds of the algebraic connectivity of G are also obtained. Other best possible spectral conditions for Hamiltonian s-properties are also discussed.  相似文献   

7.
8.
9.
《Discrete Mathematics》2023,346(4):113304
In 1965 Erd?s asked, what is the largest size of a family of k-element subsets of an n-element set that does not contain a matching of size s+1? In this note, we improve upon a recent result of Frankl and resolve this problem for s>101k3 and (s+1)k?n<(s+1)(k+1100k).  相似文献   

10.
11.
12.
Minimal blocking sets in PG(2,q2) have size at most q3+1. This result is due to Bruen and Thas and the bound is sharp, sets attaining this bound are called unitals. In this paper, we show that the second largest minimal blocking sets have size at most q3+1(p3)/2, if q=p, p67, or q=ph, p>7, h>1. Our proof also works for sets having at least one tangent at each of its points (that is, for tangency sets).  相似文献   

13.
14.
15.
16.
17.
18.
19.
20.
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号