共查询到20条相似文献,搜索用时 671 毫秒
1.
2.
《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. 相似文献
3.
4.
6.
7.
8.
《Discrete Mathematics》2022,345(10):113004
Let G be a graph. We say that G is perfectly divisible if for each induced subgraph H of G, can be partitioned into A and B such that is perfect and . We use and to denote a path and a cycle on t vertices, respectively. For two disjoint graphs and , we use to denote the graph with vertex set and edge set , and use to denote the graph with vertex set and edge set . In this paper, we prove that (i) -free graphs are perfectly divisible, (ii) if G is -free with , (iii) if G is -free, and (iv) if G is -free. 相似文献
9.
We characterize all finite metabelian 2-groups G whose abelianizations are of type , with , and for which their commutator subgroups have . This is given in terms of the order of the abelianizations of the maximal subgroups and the structure of the abelianizations of those normal subgroups of index 4 in G. We then translate these group theoretic properties to give a characterization of number fields k with 2-class group , , such that the rank of where is the Hilbert 2-class field of k. In particular, we apply all this to real quadratic number fields whose discriminants are a sum of two squares. 相似文献
11.
12.
13.
《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 . 相似文献
14.
15.
In this paper, we investigate the existence of multiple radial sign-changing solutions with the nodal characterization for a class of Kirchhoff type problems where , are radial and bounded away from below by positive numbers. Under some weak assumptions on , by taking advantage of the Gersgorin disc's theorem and Miranda theorem, we develop some new analytic techniques and prove that this problem admits infinitely many nodal solutions having a prescribed number of nodes k, whose energy is strictly increasing in k. Moreover, the asymptotic behaviors of as are established. These results improve and generalize the previous results in the literature. 相似文献
16.
17.
18.
19.