共查询到20条相似文献,搜索用时 31 毫秒
1.
《Discrete Mathematics》2022,345(5):112786
Let G be a connected graph with vertices and edges. The nullity of G, denoted by , is the multiplicity of eigenvalue zero of the adjacency matrix of G. Ma, Wong and Tian (2016) proved that unless G is a cycle of order a multiple of 4, where is the elementary cyclic number of G and is the number of leaves of G. Recently, Chang, Chang and Zheng (2020) characterized the leaf-free graphs with nullity , thus leaving the problem to characterize connected graphs G with nullity when . In this paper, we solve this problem completely. 相似文献
2.
3.
4.
5.
6.
7.
8.
9.
《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 , then G is Hamilton-connected () or Hamiltonian () or traceable (). 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 , Hamiltonian if , and traceable if .For a real number , and for a k-connected graph G with order n, degree diagonal matrix and adjacency matrix , we have identified best possible upper bounds for the spectral radius , 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. 相似文献
10.
《Discrete Mathematics》2022,345(8):112919
11.
《Discrete Mathematics》2022,345(8):112902
For a simple graph G, denote by n, , and its order, maximum degree, and chromatic index, respectively. A graph G is edge-chromatic critical if and for every proper subgraph H of G. Let G be an n-vertex connected regular class 1 graph, and let be obtained from G by splitting one vertex of G into two vertices. Hilton and Zhao in 1997 conjectured that must be edge-chromatic critical if , and they verified this when . In this paper, we prove it for . 相似文献
12.
13.
14.
《Discrete Mathematics》2022,345(12):113083
Let G be a graph, the order of G, the connectivity of G and k a positive integer such that . Then G is said to be k-extendable if it has a matching of size k and every matching of size k extends to a perfect matching of G. A Hamiltonian path of a graph G is a spanning path of G. A bipartite graph G with vertex sets and is defined to be Hamiltonian-laceable if such that and for every pair of vertices and , there exists a Hamiltonian path in G with endpoints p and q, or and for every pair of vertices , there exists a Hamiltonian path in G with endpoints p and q. Let G be a bipartite graph with bipartition . Define to be a maximum integer such that and (1) for each non-empty subset S of X, if , then , and if , then ; and (2) for each non-empty subset S of Y, if , then , and if , then ; and (3) if there is no non-negative integer satisfying (1) and (2).Let G be a bipartite graph with bipartition such that and . In this paper, we show that if , then G is Hamiltonian-laceable; or if , then for every pair of vertices and , there is an -path P in G with . We show some of its corollaries in k-extendable, bipartite graphs and a conjecture in k-extendable graphs. 相似文献
15.
16.
17.
18.
19.
《Discrete Mathematics》2022,345(12):113078
Let G be a simple connected graph and let be the sum of the first k largest Laplacian eigenvalues of G. It was conjectured by Brouwer in 2006 that holds for . The case was proved by Haemers, Mohammadian and Tayfeh-Rezaie [Linear Algebra Appl., 2010]. In this paper, we propose the full Brouwer's Laplacian spectrum conjecture and we prove the conjecture holds for which also confirm the conjecture of Guan et al. in 2014. 相似文献
20.