Search

Win conjectured that a graph G on n vertices contains k disjoint perfect matchings, if the degree sum of any two nonadjacent vertices is at least n + k - 2, where n is even and n ≥ k + 2. In this paper, we prove that Win's conjecture is true for k ≥ n/2, where n is sufficiently large. To show this result, we prove a theorem on k-factor in a graph under some Ore-type condition. Our main tools include Tutte's k-factor theorem, the Karush-Kuhn-Tucker theorem on convex optimization and the solution to the long-standing 1-factor decomposition conjecture. [ABSTRACT FROM AUTHOR]

Let G 1 , G 2 , ... , G c be arbitrary graphs. By G → (G 1 , G 2 , ... , G c) , we mean if the edges of G are partitioned into c disjoint color classes giving c graphs H 1 , H 2 , ... , H c , then at least one H i has a subgraph isomorphic to G i. The Ramsey number R (G 1 , G 2 , ... , G c) is the smallest positive integer n such that K n → (G 1 , G 2 , ... , G c). In this paper, we extend the result of Cockayne and Lorimer on the Ramsey number of stripes allowing host graphs with the corresponding Ore-type condition: If t ≥ 1 and n 1 , n 2 , ... , n c , n 1 = max ⁡ { n 1 , n 2 , ... , n c } , are positive integers and G is a graph with at least max ⁡ { t , n 1 } + ∑ i = 1 c (n i − 1) + 1 vertices such that for each pair of non-adjacent vertices, the sum of the number of their non-neighbors is at most 2 max ⁡ { t , n 1 } − 1 , then G → (n 1 K 2 , n 2 K 2 , ... , n c K 2). Consequently, we prove that if G is a graph with chromatic number at least max ⁡ { t , n 1 } + ∑ i = 1 c (n i − 1) + 1 , then G → (S t , n 1 K 2 , n 2 K 2 , ... , n c K 2) , where S t is the star graph with t edges. In addition, for given graph G , the Ramsey closure of G , denoted by C (G) , is defined and we prove that if G is a graph with at least max ⁡ { t , n 1 } + ∑ i = 1 c (n i − 1) + 1 vertices, then G → (n 1 K 2 , n 2 K 2 , ... , n c K 2) if and only if C (G) → (n 1 K 2 , n 2 K 2 , ... , n c K 2). Thus, a condition that forces C (G) → (n 1 K 2 , n 2 K 2 , ... , n c K 2) also forces G → (n 1 K 2 , n 2 K 2 , ... , n c K 2). As a result, a condition is provided on the degree sequence of a graph G such that under this condition G → (n 1 K 2 , n 2 K 2 , ... , n c K 2). Further, this article provides a sharp bound for the maximum number of edges in a simple graph G such that G ↛ (n 1 K 2 , n 2 K 2 , ... , n c K 2). We also establish the uniqueness of such extremal graphs. This result provides a far-reaching generalization of an important classical result of Erdős and Gallai and also giving a new proof for the graph case of the conjecture of Erdős dating back to 1965, known as the Erdős' matching conjecture. [ABSTRACT FROM AUTHOR]

Let S1 and S2 be two (k − 1)-subsets in a k-uniform hypergraph H. We call S1 and S2 strongly or middle or weakly independent if H does not contain an edge e ∈ E(H) such that S1 ∩ e ≠ ∅ and S2 ∩ e ≠ ∅ or e ⊆ S1 ∪ S2 or e ⊇ S1 ∪ S2, respectively. In this paper, we obtain the following results concerning these three independence. (1) For any n ≥ 2k2 − k and k ≥ 3, there exists an n-vertex k-uniform hypergraph, which has degree sum of any two strongly independent (k − 1)-sets equal to 2n−4(k−1), contains no perfect matching; (2) Let d ≥ 1 be an integer and H be a k-uniform hypergraph of order n ≥ kd+(k−2)k. If the degree sum of any two middle independent (k−1)-subsets is larger than 2(d−1), then H contains a d-matching; (3) For all k ≥ 3 and sufficiently large n divisible by k, we completely determine the minimum degree sum of two weakly independent (k − 1)-subsets that ensures a perfect matching in a k-uniform hypergraph H of order n. [ABSTRACT FROM AUTHOR]

A graph is called traceable if it contains a Hamilton path, i.e., a path containing all its vertices. Let G be a graph on n vertices. We say that an induced subgraph of G is o−1-heavy if it contains two nonadjacent vertices which satisfy an Ore-type degree condition for traceability, i.e., with degree sum at least n−1 in G. A block-chain is a graph whose block graph is a path, i.e., it is either a P1, P2, or a 2-connected graph, or a graph with at least one cut vertex and exactly two end-blocks. Obviously, every traceable graph is a block-chain, but the reverse does not hold. In this paper we characterize all the pairs of connected o−1-heavy graphs that guarantee traceability of block-chains. Our main result is a common extension of earlier work on degree sum conditions, forbidden subgraph conditions and heavy subgraph conditions for traceability