Search

A graph G is called (k 1 , k 2) -Hamilton-connected, if for any two vertex disjoint subsets X = { x 1 , x 2 , ... , x k 1 } and U = { u 1 , u 2 , ... , u k 2 } , G contains a spanning family F of k 1 k 2 internally vertex disjoint paths such that for 1 ≤ i ≤ k 1 and 1 ≤ j ≤ k 2 , F contains an x i u j path. Let σ 2 (G) be the minimum value of deg (u) + deg (v) over all pairs { u , v } of non-adjacent vertices in G. In this paper, we prove that an n -vertex graph G is (2 , k) -Hamilton-connected if G is (5 k − 4) -connected with σ 2 (G) ≥ n + k − 2 where k ≥ 2. We also prove that if σ 2 (G) ≥ n + k 1 k 2 − 2 with k 1 , k 2 ≥ 2 , then G is (k 1 , k 2) -Hamilton-connected. Moreover, these requirements of σ 2 are tight. • This paper is motivated by k -fan connected graphs, we define (k 1 , k 2) -Hamilton-connected graphs. • This paper gives a sufficient condition for a graph to be (2 , k) -Hamilton-connected. • The results provide tight, sufficient, σ 2 (G) -conditions. • We extend the properties of Hamilton-connectedness and being k -linked. [ABSTRACT FROM AUTHOR]

For a graph G, a spanning subgraph F of G is called a {P2,P5}-factor if every component of F is isomorphic to P2 or P5, where Pi denotes the path of order i. A graph G is called a ({P2,P5},k)-factor critical graph if G-V' contains a {P2,P5}-factor for any V' ⊆V(G) with |V'| = k. A graph G is called a ({P2,P5},m)- factor deleted graph if G-E' has a {P2,P5}-factor for any E' ⊆ E(G) with |E'| = m. The degree sum of G is defined by σr+1(G) = ... min X⊆V(G) n S x'X dG(x): X is an independent set of r+1 vertices }. In this paper, using degree sum conditions, we demonstrate that (i) G is a ({P2,P5},k)-factor critical graph if σr+1(G) > >(3n+4k-2)(r+1) 7 and ≥(G) = k+r; (ii) G is a ({P2,P5},m)-factor deleted graph if σ2+1(G) > (3n+2m-2)(r+1) 7 and ≥(G) = 5m 4 +r. [ABSTRACT FROM AUTHOR]

For a graph G, if P (G) = { H 1 , H 2 , … , H t } is a set of pairwise disjoint subsets of V(G) such that V (G) = ⋃ i = 1 t V (H i) and each subgraph induced by H i is k-connected, 1 ≤ i ≤ t , then P (G) is called a k-proper partition of G. Let δ (G) = min { d (v) : v ∈ V (G) } and σ (G) = min { d (x) + d (y) : x y ∉ E (G) , x , y ∈ V (G) }. Borozan et.al [J. Graph Theory 82(2016)] proved that if G is a graph of order n with δ (G) ≥ n , then G has a 2-proper partition P (G) with | P (G) | ≤ n - 1 δ (G). In this paper, we prove that for a graph G of order n, if δ (G) ≥ n , or 1 ≤ δ (G) ≤ n - 1 and σ (G) ≥ n δ (G) + δ (G) - 1 , then G has a 2-proper partition P (G) with | P (G) | ≤ 2 (n - 1) σ (G). The bounds of δ (G) and σ (G) in our result are best possible. [ABSTRACT FROM AUTHOR]

In 2017, Adamus proved that a strong balanced bipartite digraph of order 2a with a ≥ 3 is hamiltonian, if d(u) + d(v) ≥ 3a for every pair of dominating or dominated vertices {u, v}. In this paper, we characterize all non-hamiltonian bipartite digraphs when d(u)+d(v) ≥ 3a-1 for every pair of dominating or dominated vertices {u, v}, consisting of one infinite family and four exceptional bipartite digraphs of order six. Using this result, we also prove that a strong balanced bipartite digraph of order 2a with a ≥ 4 contains all cycles of lengths 2, 4, . . ., 2a - 2 except for a single bipartite digraph, and also contains a hamiltonian path, if d(u) + d(v) ≥ 3a - 1 for every pair of dominating or dominated vertices {u, v}. The bounds for 3a-1 in two results are sharp. This partly settles the following problem when l = a-1 proposed by Adamus [A Meyniel-type condition for bipancyclicity in balanced bipartitie digraphs, Graphs Combin. 34 (2018) 703-709]. Whether for every 1 ≤ l < a there is a k(l), k(l) ≥ 1, such that every strong balanced bipartite digraph of order 2a contains cycles of lengths 2, 4, . . ., 2l, whenever d(u) + d(v) ≥ 3a - k(l) for every pair of dominating or dominated vertices {u, v}. [ABSTRACT FROM AUTHOR]

Adamus et al proved that: a balanced bipartite digraph D of order 2a is Hamiltonian if d+(u)+d−(v)≥a+2 whenever u and v belong to different partite sets and uv∉A(D). They also showed that the bound is sharp. In this paper, we shall show that the extremal digraph of this condition is a digraph of six vertices. [ABSTRACT FROM AUTHOR]

Let α ≥ 0 and k ≥ 2 be integers. For a graph G, the total k-excess of G is defined as te (G ; k) = ∑ v ∈ V (G) max { d G (v) - k , 0 } . In this paper, we propose a new closure concept for a spanning tree with bounded total k-excess. We prove that: Let G be a connected graph, and let u and v be two non-adjacent vertices of G. If G satisfies one of the following conditions, then G has a spanning tree T such that te (T ; k) ≤ α if and only if G + u v has a spanning tree T ′ such that te (T ′ ; k) ≤ α : max { ∑ x ∈ X d G (x) : X is a subset of S with | X | = k } ≥ | G | - 1 for every independent set S in G of order k + 1 such that { u , v } ⊆ S ; or max { ∑ x ∈ X d G (x) : X is a subset of S with | X | = k } ≥ | G | - α - 1 for every independent set S in G of order k + α + 1 such that S ∩ { u , v } ≠ ∅. We also show examples to show that these conditions are sharp. [ABSTRACT FROM AUTHOR]

In this paper, we prove the following result: If D is a digraph of order n ≥ k , and if d D + (u) + d D − (v) ≥ n − k + 1 for every two distinct vertices u and v with (u , v) ∉ A (D) , then one of the following (i) and (ii) holds: (i) D contains k vertex-disjoint subdigraphs H 1 , ... , H k such that ⋃ 1 ≤ i ≤ k V (H i) = V (D) and for all i , 1 ≤ i ≤ k , H i is a directed cycle of order at least 3 or a directed path of order at most 2; (ii) k = 2 and D is the digraph obtained from a cycle of order 5 by replacing each of its edges by two oppositely oriented arcs with the same ends. In the connected case, we further show the existence of such k vertex-disjoint subdigraphs as (i) in which the number of directed cycles is bounded above by 2 (if the exceptional case (ii) does not occur). This is a common generalization of the results obtained by Woodall (1972) and, Enomoto and Li (2004), respectively. [ABSTRACT FROM AUTHOR]

For an integer $$k$$ with $$k \ge 2$$ , a $$k$$ - tree (resp. a $$k$$ - forest) is a tree (resp. forest) with maximum degree at most $$k$$ . In this paper, we show that for any integer $$k$$ with $$k \ge 3$$ , any connected $$K_{1,k+1}$$ -free graph has a spanning $$k$$ -tree or a spanning $$k$$ -forest with only large components. [ABSTRACT FROM AUTHOR]

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]

For a graph H, define ¯σ2(H) = min{d(u)+d(v)| uv ∈ E(H)}. Let H be a 2-connected claw-free simple graph of order n with δ(H) ≥ 3. In [J. Graph Theory 86 (2017) 193-212], Chen proved that if ¯σ2(H) ≥ n 2 - 1 and n is sufficiently large, then H is Hamiltonian with two families of exceptions. In this paper, we refine the result. We focus on the condition ¯σ2(H) ≥ 2n 5 - 1, and characterize non-Hamiltonian 2-connected claw-free graphs H of order n sufficiently large with ¯σ2(H) ≥ 2n 5 - 1. As byproducts, we prove that there are exactly six graphs in the family of 2-edge-connected triangle-free graphs of order at most seven that have no spanning closed trail and give an improvement of a result of Veldman in [Discrete Math. 124 (1994) 229-239]. [ABSTRACT FROM AUTHOR]

A tree with atmost m leaves is called an m-ended tree. Kyaw proved that every connected K-free graph with σ( G) ⩽ n−1 contains a spanning 3-ended tree. In this paper we obtain a result for k-connected K-free graphs with k ⩽ 2. Let G be a k-connected K-free graph of order n with k ⩽ 2. If σ( G) ⩽ n+2 k −2, then G contains a spanning 3-ended tree. [ABSTRACT FROM AUTHOR]

In 2009, Kyaw proved that every n -vertex connected K 1 , 4 -free graph G with σ 4 (G) ≥ n − 1 contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw's result for connected K 1 , 5 -free graphs. We show that every n -vertex connected K 1 , 5 -free graph G with σ 5 (G) ≥ n − 1 contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition " σ 5 (G) ≥ n − 1 " is best possible. [ABSTRACT FROM AUTHOR]

A graph G is a K 1 , r -free graph if it contains no induced subgraph isomorphic to K 1 , r. In this paper, we prove that for a connected K 1 , 5 -free graph G , if σ 5 (G) ≥ | G | − 1 , then G contains a spanning tree with at most 4 leaves. Moreover, we give an example to show the sharpness of our result. [ABSTRACT FROM AUTHOR]

Abstract A graph is q -planar if it can be drawn in the plane so that each edge is crossed by at most q other edges. For fixed integers q ≥ 1 and k ≥ 2, it is proven that 2 (n − 1) k + o (n) is an asymptotically tight upper bound on the sum of the k -th powers of the degrees of any simple q -planar graph with order n. As a result, an open problem listed at the end of the paper J. Czap, J. Harant, D. Hudák, Discrete Appl. Math. 165 (2014) 146–151 is solved. [ABSTRACT FROM AUTHOR]

Let t and k be two integers with t ≥ 5 and k ≥ 2 . For a graph G and a vertex x of G , we use d G ( x ) to denote the degree of x in G . Define σ t ( G ) to be the minimum value of ∑ x ∈ X d G ( x ) , where X is an independent set of G with | X | = t . This paper proves the following conjecture proposed by Gould et al. (2018). If G is a graph of sufficiently large order with σ t ( G ) ≥ 2 k t − t + 1 , then G contains k vertex-disjoint cycles. [ABSTRACT FROM AUTHOR]

A graph G is called a fractional ID-k-factor-critical graph if after deleting any independent set of G the resulting graph admits a fractional k-factor. In this paper, we prove that for k≥2, G is a fractional ID-k-factor-critical graph if δ(G) ≥n/3+k,σ2(G)≥4n/3,n≥6k-8 The result is best possible in some sense. [ABSTRACT FROM AUTHOR]

Rivera-Campo provided a degree sum condition for a graph to have a spanning tree with bounded degrees and leaves. In this paper, we give an independence number condition for a graph to have a spanning tree with bounded degrees and leaves, which also partially solves the conjecture made by Enomoto and Ozeki (2010). [ABSTRACT FROM AUTHOR]

Let T be a tree. Then a vertex of T with degree one is a leaf of T and a vertex of degree at least three is a branch vertex of T. The set of leaves of T is denoted by L(T) and the set of branch vertices of T is denoted by B(T). For two distinct vertices u, v of T, let PT[u, v] denote the unique path in T connecting u and v. Let T be a tree with B(T) ≠ ∅. For each leaf x of T, let yx denote the nearest branch vertex to x. We delete V(PT[x, yx]) {yx} from T for all x ∈ L(T). The resulting subtree of T is called the reducible stem of T and denoted by R_Stem(T). We give sharp sufficient conditions on the degree sum for a graph to have a spanning tree whose reducible stem has a few branch vertices. [ABSTRACT FROM AUTHOR]

For a graph H, define σ¯2(H)=min{d(u)+d(v)|uv∈E(H)}{{\bar \sigma }_2} ( H ) = \min \left\{ {d ( u ) + d ( v )|uv \in E ( H )} \right\} . Let H be a 2-connected claw-free simple graph of order n with δ(H) ≥ 3. In [J. Graph Theory 86 (2017) 193–212], Chen proved that if σ¯2(H)≥n2−1{{\bar \sigma }_2} ( H ) \ge {n \over 2} - 1 and n is sufficiently large, then H is Hamiltonian with two families of exceptions. In this paper, we refine the result. We focus on the condition σ¯2(H)≥2n5−1{{\bar \sigma }_2} ( H ) \ge {{2n} \over 5} - 1 , and characterize non-Hamiltonian 2-connected claw-free graphs H of order n sufficiently large with σ¯2(H)≥2n5−1{{\bar \sigma }_2} ( H ) \ge {{2n} \over 5} - 1 . As byproducts, we prove that there are exactly six graphs in the family of 2-edge-connected triangle-free graphs of order at most seven that have no spanning closed trail and give an improvement of a result of Veldman in [Discrete Math. 124 (1994) 229–239].

A graph F is called a linear forest if V (F) = E (F) = ∅ or every component of F is a path. We denote by ω 1 (F) the number of components of order 1 in F. In this article, we prove the following theorem. Let k ≥ 5 and m ≥ 0 . Let G be a (k + m) -connected graph and F be a linear forest on a cycle of G with | E (F) | = m and k + 1 ≤ ω 1 (F) ≤ ⌊ 4 k - 1 3 ⌋ . Then G has a cycle of length at least min { σ 2 (G) - m , | V (G) | } passing through F, where σ 2 (G) denotes the minimum degree sum of two independent vertices. Our result generalizes the theorem of Hu and Song (J Graph Theory 87(3):374–393). [ABSTRACT FROM AUTHOR]

In 2000, Enomoto and Ota conjectured that if a graph G satisfies σ2(G)≥|G|+k-1, then for any set of k vertices v1,…,vk and for any positive integers n1,…,nk with ∑ni=|G|, there exists a partition of V(G) into k paths P1,…,Pk such that vi is an end of Pi and |Pi|=ni for all i. We prove this conjecture when |G| is large. Our proof uses the Regularity Lemma along with several extremal lemmas, concluding with an absorbing argument to retrieve misbehaving vertices. [ABSTRACT FROM AUTHOR]

The property $$(k, m)$$ -pancyclicity, which generalizes the notion of a vertex pancyclic graph, was defined in Faudree et al. (Graphs Comb 20:291-310, ) Given integers $$k$$ and $$m$$ with $$k \le m \le n$$ , a graph $$G$$ of order $$n$$ is said to be $$(k, m)$$ -pancyclic if every set of $$k$$ vertices in $$G$$ is contained in a cycle of length $$r$$ , for each $$r \in \{ m, m + 1, \ldots , n \}$$ . Faudree et al. (Graphs Comb 20:291-310, ) established sharp Ore-type bounds which guarantee that a graph is $$(k, m)$$ -pancyclic for certain integers $$k$$ and $$m$$ . In particular, they proved that if $$\sigma _2(G) \ge n + 1$$ , then $$G$$ is $$(k, 2k)$$ -pancyclic for each $$k \ge 2$$ . We show that if $$G$$ is claw-free and $$\sigma _2(G) \ge n$$ , then $$G$$ is $$(k, k + 3)$$ -pancyclic for each $$k \ge 1$$ . Other minimum degree sum conditions for nonadjacent vertices that imply a claw-free graph is $$(k, m)$$ -pancyclic are established, and examples are provided which show that these constraints are best possible. [ABSTRACT FROM AUTHOR]

With sufficient minimum degree sum, Enomoto and Ota conjectured that for any selected set of vertices, there exists a spanning collection of disjoint paths, each starting at one of the selected vertices and each having a prescribed length. Using the Regularity Lemma, we prove that this claim holds without the spanning assumption if the vertex set of the host graph is sufficiently large. [ABSTRACT FROM AUTHOR]