共查询到20条相似文献,搜索用时 46 毫秒
1.
2.
3.
《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. 相似文献
4.
《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 . 相似文献
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.
9.
10.
《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 . 相似文献
11.
12.
13.
14.
15.
《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. 相似文献
16.
《Discrete Mathematics》2022,345(3):112731
Let be the matching number of a graph G. A characterization of the graphs with given maximum odd degree and smallest possible matching number is given by Henning and Shozi (2021) [13]. In this paper we complete our study by giving a characterization of the graphs with given maximum even degree and smallest possible matching number. In 2018 Henning and Yeo [10] proved that if G is a connected graph of order n, size m and maximum degree k where is even, then , unless G is k-regular and . In this paper, we give a complete characterization of the graphs that achieve equality in this bound when the maximum degree k is even, thereby completing our study of graphs with given maximum degree and smallest possible matching number. 相似文献
17.
18.
《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. 相似文献
19.
《Discrete Mathematics》2022,345(12):113082
Let G be a graph of order n with an edge-coloring c, and let denote the minimum color-degree of G. A subgraph F of G is called rainbow if all edges of F have pairwise distinct colors. There have been a lot of results on rainbow cycles of edge-colored graphs. In this paper, we show that (i) if , then every vertex of G is contained in a rainbow triangle; (ii) if and , then every vertex of G is contained in a rainbow ; (iii) if G is complete, and , then G contains a rainbow cycle of length at least k, where . 相似文献