共查询到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.
《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. 相似文献
5.
6.
7.
《Discrete Mathematics》2022,345(3):112717
A transversal set of a graph G is a set of vertices incident to all edges of G. The transversal number of G, denoted by , is the minimum cardinality of a transversal set of G. A simple graph G with no isolated vertex is called τ-critical if for every edge . For any τ-critical graph G with , it has been shown that by Erd?s and Gallai and that by Erd?s, Hajnal and Moon. Most recently, it was extended by Gyárfás and Lehel to . In this paper, we prove stronger results via spectrum. Let G be a τ-critical graph with and , and let denote the largest eigenvalue of the adjacency matrix of G. We show that with equality if and only if G is , , or , where ; and in particular, with equality if and only if G is . We then apply it to show that for any nonnegative integer r, we have and characterize all extremal graphs. This implies a pure combinatorial result that , which is stronger than Erd?s-Hajnal-Moon Theorem and Gyárfás-Lehel Theorem. We also have some other generalizations. 相似文献
8.
《Discrete Mathematics》2022,345(8):112904
Let be the minimum integer such that every plane graph with girth g at least , minimum degree and no -paths consisting of vertices of degree 2, where , has a 3-vertex with at least t neighbors of degree 2, where .In 2015, Jendrol' and Maceková proved . Later on, Hudák et al. established , Jendrol', Maceková, Montassier, and Soták proved , and , and we recently proved that and .Thus is already known for and all t. In this paper, we prove that , , and whenever . 相似文献
9.
10.
11.
12.
13.
《Discrete Mathematics》2022,345(12):113158
In 2016, McDiarmid and Yolov gave a tight threshold for the existence of Hamilton cycle in graphs with large minimum degree and without large “bipartite hole”(two disjoint sets of vertices with no edge between them) which extends Dirac's classical Theorem. In detail, an -bipartite-hole in a graph G consists of two disjoint vertex sets S and T with and such that . Let be the maximum integer such that G contains an -bipartite-hole for every pair of nonnegative integers s and t with . Motivated by Bondy's metaconjecture, in this paper, we study the existence of vertex-pancyclicity (every vertex is in a cycle of length i for each and Hamilton-connectivity(any two vertices can be connected through a Hamilton path). Our central theorem is that for any given and sufficiently large n, if G is an n-vertex graph with and , then G is Hamilton-connected and vertex-pancyclic. 相似文献
14.
15.
《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 ? The second asks which graph attains the maximum Q-index over all -bipartite graphs with edges? We solve the first question for , and the second question for . The maximum Q-index on connected -bipartite graphs is also determined for . 相似文献
16.
《Discrete Mathematics》2021,344(12):112604
A well-known theorem of Vizing states that if G is a simple graph with maximum degree Δ, then the chromatic index of G is Δ or . A graph G is class 1 if , and class 2 if ; G is Δ-critical if it is connected, class 2 and for every . A long-standing conjecture of Vizing from 1968 states that every Δ-critical graph on n vertices has at least edges. We initiate the study of determining the minimum number of edges of class 1 graphs G, in addition, for every . Such graphs have intimate relation to -co-critical graphs, where a non-complete graph G is -co-critical if there exists a k-coloring of such that G does not contain a monochromatic copy of but every k-coloring of contains a monochromatic copy of for every . We use the bound on the size of the aforementioned class 1 graphs to study the minimum number of edges over all -co-critical graphs. We prove that if G is a -co-critical graph on vertices, then where ε is the remainder of when divided by 2. This bound is best possible for all and . 相似文献
17.
18.
《Discrete Mathematics》2022,345(8):112919
19.
20.
《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 . 相似文献