共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
《Discrete Mathematics》2022,345(8):112919
3.
4.
5.
6.
7.
《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 . 相似文献
8.
9.
10.
11.
12.
14.
《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 ? In this note, we improve upon a recent result of Frankl and resolve this problem for and . 相似文献
15.
16.
《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. 相似文献
17.
19.
《Discrete Mathematics》2022,345(2):112675
We consider the binomial random graph , where p is a constant, and answer the following two questions.First, given , what is the maximum k such that a.a.s. the binomial random graph has an induced subgraph with k vertices and edges? We prove that this maximum is not concentrated in any finite set (in contrast to the case of a small ). Moreover, for every constant , with probability bounded away from 0, the size of the concentration set is bigger than , and, for every , a.a.s. it is smaller than .Second, given , what is the maximum μ such that a.a.s. the set of sizes of k-vertex subgraphs of contains a full interval of length μ? The answer is . 相似文献
20.
《Discrete Mathematics》2023,346(5):113344
For any positive integer k, let denote the least integer such that any n-vertex graph has an induced subgraph with at least vertices, in which at least vertices are of the same degree. Caro, Shapira and Yuster initially studied this parameter and showed that . For the first nontrivial case, the authors proved that , and the exact value was left as an open problem. In this paper, we first show that , improving the former result as well as a recent result of Kogan. For special families of graphs, we prove that for -free graphs, and for large -free graphs. In addition, extending a result of Erd?s, Fajtlowicz and Staton, we assert that every -free graph is an induced subgraph of a -free graph in which no degree occurs more than three times. 相似文献