共查询到20条相似文献,搜索用时 31 毫秒
1.
Sergei Bezrukov Dalibor Fronček Steven J. Rosenberg Petr Kovář 《Discrete Mathematics》2008,308(2-3):319-323
2.
In 1962, Erd?s proved that if a graph with vertices satisfies where the minimum degree and , then it is Hamiltonian. For , let , where “” is the “join” operation. One can observe and is not Hamiltonian. As contains induced claws for , a natural question is to characterize all 2-connected claw-free non-Hamiltonian graphs with the largest possible number of edges. We answer this question completely by proving a claw-free analog of Erd?s’ theorem. Moreover, as byproducts, we establish several tight spectral conditions for a 2-connected claw-free graph to be Hamiltonian. Similar results for the traceability of connected claw-free graphs are also obtained. Our tools include Ryjá?ek’s claw-free closure theory and Brousek’s characterization of minimal 2-connected claw-free non-Hamiltonian graphs. 相似文献
3.
Zoltán Füredi Alexandr Kostochka Ruth Luo Jacques Verstraëte 《Discrete Mathematics》2018,341(5):1253-1263
The Erd?s–Gallai Theorem states that for , any -vertex graph with no cycle of length at least has at most edges. A stronger version of the Erd?s–Gallai Theorem was given by Kopylov: If is a 2-connected -vertex graph with no cycle of length at least , then , where . Furthermore, Kopylov presented the two possible extremal graphs, one with edges and one with edges.In this paper, we complete a stability theorem which strengthens Kopylov’s result. In particular, we show that for odd and all , every -vertex 2-connected graph with no cycle of length at least is a subgraph of one of the two extremal graphs or . The upper bound for here is tight. 相似文献
4.
5.
Füredi conjectured that the Boolean lattice can be partitioned into chains such that the size of any two differs in at most one. In this paper, we prove that there is an absolute constant with the following property: for every , if is sufficiently large, the Boolean lattice has a chain partition into chains, each of them of size between and .We deduce this result by looking at the more general setup of unimodal normalized matching posets. We prove that a unimodal normalized matching poset of width has a chain partition into chains, each of size at most , and it has a chain partition into chains, where each chain has size at least . 相似文献
6.
7.
8.
9.
A graph is packable if it is a subgraph of its complement. The following statement was conjectured by Faudree, Rousseau, Schelp and Schuster in 1981: every non-star graph with girth at least is packable.The conjecture was proved by Faudree et al. with the additional condition that has at most edges. In this paper, for each integer , we prove that every non-star graph with girth at least and at most edges is packable, where is for every . This implies that the conjecture is true for sufficiently large planar graphs. 相似文献
10.
11.
12.
There are many generalizations of the Erdős–Ko–Rado theorem. Here the new results (and problems) concern families of -intersecting -element multisets of an -set. We point out connections to coding theory and geometry. We verify the conjecture that for such a family can have at most members. 相似文献
13.
15.
16.
17.
18.
19.
In this paper, we consider combinatorial numbers , mentioned as Catalan triangle numbers where . These numbers unify the entries of the Catalan triangles and for appropriate values of parameters and , i.e., and . In fact, these numbers are suitable rearrangements of the known ballot numbers and some of these numbers are the well-known Catalan numbers that is .We present identities for sums (and alternating sums) of , squares and cubes of and, consequently, for and . In particular, one of these identities solves an open problem posed in Gutiérrez et al. (2008). We also give some identities between and harmonic numbers . Finally, in the last section, new open problems and identities involving are conjectured. 相似文献
20.