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]

We denote by G[ X, Y] a bipartite graph G with partite sets X and Y. Let d( v) be the degree of a vertex v in a graph G. For G[ X, Y] and $${S \subseteq V(G),}$$ we define $${\sigma_{1,1}(S):=\min\{d_G(x)+d_G(y) : (x,y) \in (X \cap S,Y) \cup (X, Y \cap S), xy \not\in E(G)\}}$$ . Amar et al. (Opusc. Math. 29:345-364, ) obtained σ( S) condition for cyclability of balanced bipartite graphs. In this paper, we generalize the result as it includes the case of unbalanced bipartite graphs: if G[ X, Y] is a 2-connected bipartite graph with | X| ≥ | Y| and $${S \subseteq V(G)}$$ such that σ( S) ≥ | X| + 1, then either there exists a cycle containing S or $${|S \cap X| > |Y|}$$ and there exists a cycle containing Y. This degree sum condition is sharp. [ABSTRACT FROM AUTHOR]

Let G be a graph. We denote p( G) and c( G) the order of a longest path and the order of a longest cycle of G, respectively. Let κ( G) be the connectivity of G, and let σ( G) be the minimum degree sum of an independent set of three vertices in G. In this paper, we prove that if G is a 2-connected graph with p( G) − c( G) ≥ 2, then either (i) c( G) ≥ σ( G) − 3 or (ii) κ( G) = 2 and p( G) ≥ σ( G) − 1. This result implies several known results as corollaries and gives a new lower bound of the circumference. [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 1972, Woodall raised the following Ore-type condition for directed Hamilton cycles in digraphs: Let D be a digraph. If for every vertex pair u and v, where there is no arc from u to v, we have d+(u) + d-(v) ≥ |D|, then D has a directed Hamilton cycle. By a correspondence between bipartite graphs and digraphs, the above result is equivalent to the following result of Las Vergnas: Let G = (B, W) be a balanced bipartite graph. If for any b ∈ B and w ∈ W, where b and w are nonadjacent, we have d(w) + d(b) ≥ |G|/2 + 1, then every perfect matching of G is contained in a Hamilton cycle. The lower bounds in both results are tight. In this paper, we reduce both bounds by 1 and prove that the conclusions still hold, with only a few exceptional cases that can be clearly characterized. [ABSTRACT FROM AUTHOR]

For a graph G, δ( G) denotes the minimum degree of G. In 1971, Bondy proved that, if G is a 2-connected graph of order n and d( x) + d( y) ≥ n for each pair of non-adjacent vertices x, y in G, then G is pancyclic or G = K. In 2001, Xu proved that, if G is a 2-connected graph of order n ≥ 6 and | N( x) ∪ N( y)| + δ( G) ≥ n for each pair of non-adjacent vertices x, y in G, then G is pancyclic or G = K. In this paper, we introduce a new sufficient condition of generalizing degree sum and neighborhood union and prove that, if G is a 2-connected graph of order n ≥ 6 and | N( x) ∪ N( y)| + d( w) ≥ n for any three vertices x, y, w of d( x, y) = 2 and wx or $wy\not\in E(G)$ in G, then G is 4-vertex pancyclic or G belongs to two classes of well-structured exceptional graphs. This result also generalizes the above results. [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 k-tree is a tree with maximum degree at most k. In this paper, we give sufficient conditions for a graph to have a k-tree containing specified vertices. Let k be an integer with k ≥ 3. Let G be a graph of order n and let S ⊆ V(G) with ?(S) ≥ 1. Suppose that for every l ≥ :(S), there exists an integer t such that 1 ≤ t ≤ (k - 1)l + 2 - [l-1/k ] and the degree sum of any t independent vertices of S is at least n +tl -kl -1. Then G has a k-tree containing S.We also show some new results on a spanning k-tree as corollaries of the above theorem. [ABSTRACT FROM AUTHOR]

Let G be a graph and S ⊂ V( G). We denote by α( S) the maximum number of pairwise nonadjacent vertices in S. For x, y ∈ V( G), the local connectivity κ( x, y) is defined to be the maximum number of internally-disjoint paths connecting x and y in G. We define $$\kappa(S)=\min\{\kappa(x,y) : x,y \in S,x\not=y\}$$ . In this paper, we show that if κ( S) ≥ 3 and $$\sum_{i=1}^4 d_{G}{(x_i)} \ge |V(G)|+\kappa(S)+\alpha (S)-1$$ for every independent set { x 1, x 2, x 3, x 4} ⊂ S, then G contains a cycle passing through S. This degree condition is sharp and this gives a new degree sum condition for a 3-connected graph to be hamiltonian. [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]

Abstract: For a graph , denotes the minimum degree of . In 1971, Bondy proved that, if is a 2-connected graph of order and for each pair of non-adjacent vertices , in , then is pancyclic or . In 2006, Wu et al. proved that, if is a 2-connected graph of order and for each pair of non-adjacent vertices , of in , then is pancyclic or . In this paper, we introduce a new condition which generalizes two conditions of degree sum and neighborhood union and prove that, if is a 2-connected graph of order and for any three vertices , , of and or in , then is pancyclic or . This result also generalizes the above two results. [Copyright &y& Elsevier]

Abstract: Let be a 2-edge-connected simple graph on vertices, let denote an abelian group with the identity element 0, and let be an orientation of . The boundary of a function is the function given by , where is the set of edges with tail and is the set of edges with head . A graph is -connected if for every with , there is a function such that . In this paper, we prove that if for each , then is not -connected if and only if is either one of specific graphs or one of or for , where denotes the graph obtained from by adding an edge joining two vertices of maximum degree. This result generalizes the result in [G. Fan, C. Zhou, Degree sum and Nowhere-zero 3-flows, Discrete Math. 308 (2008) 6233–6240] by Fan and Zhou. [ABSTRACT FROM AUTHOR]

Abstract: Let be a -connected graph of order . In , Bondy (1980) considered a degree sum condition for a graph to have a Hamiltonian cycle, say, to be covered by one cycle. He proved that if , then has a Hamiltonian cycle. On the other hand, concerning a degree sum condition for a graph to be covered by two cycles, Enomoto et al. (1995) proved that if and , then can be covered by two cycles. By these results, we conjecture that if , then can be covered by two cycles. In this paper, we prove the case of this conjecture. In fact, we prove a stronger result; if is 2-connected with , then can be covered by two cycles, or belongs to an exceptional class. [Copyright &y& Elsevier]

Abstract: In this paper, we prove that -connected graphs have either a dominating path or two disjoint paths, wherein the length of the two paths is bounded by the minimum among and a parameter defined on the neighborhood condition of any four independent vertices of the graph. [Copyright &y& Elsevier]

Abstract: For a graph , and denote the orders of a longest path and a longest cycle of , respectively. For a graph , we denote by and the degree of a vertex in and the connectivity of , respectively. In this paper, we prove that if is a 3-connected graph of order such that for every independent set , then . This is a stronger result than the problem of Lu et al. [M. Lu, H. Liu, F. Tian, Two sufficient conditions for dominating cycles, J. Graph Theory 49 (2005) 134–150], and this degree condition is sharp. [Copyright &y& Elsevier]

We conjecture Ore and Erdős type criteria for a balanced bipartite graph of order 2n to contain a long cycle C2n-2k, where 0 ≤ k < n/2. For k = 0, these are the classical hamiltonicity criteria of Moon and Moser. The main two results of the paper assert that our conjectures hold for k = 1 as well. [ABSTRACT FROM AUTHOR]

Abstract: Win, in 1975, and Jackson and Wormald, in 1990, found the best sufficient conditions on the degree sum of a graph to guarantee the properties of “having a -tree” and “having a -walk”, respectively. The property of “being prism hamiltonian” is an intermediate property between “having a 2-tree” and “having a 2-walk”. Thus, it is natural to ask what is the best degree sum condition for graphs to be prism hamiltonian. As an answer to this problem, in this paper, we show that a connected graph of order with is prism hamiltonian. The degree sum condition “” is best possible. [Copyright &y& Elsevier]

Abstract: Let be an -graph on vertices, and be a linear forest in with and , where is the number of components of order one in . We denote by the minimum value of the degree sum of three vertices which are pairwise non-adjacent. In this paper, we give several conditions for a dominating cycle or a hamiltonian cycle passing through a linear forest. We first prove that if , then every longest cycle passing through is dominating. Using this result, we prove that if then contains a hamiltonian cycle passing through . As a corollary, we obtain a result that if is a 3-connected graph and , then is hamiltonian-connected. [Copyright &y& Elsevier]

Abstract: Let be a graph. For , let denote the maximum value of the degree sums of the subsets of of order . In this paper, we prove the following two results. (1) Let be a 2-connected graph. If for every independent set of order , then has a cycle of length at least . (2) Let be a 2-connected graph and a subset of . If for every independent set of order in , then has a cycle that includes every vertex of . This suggests that the degree sum of nonadjacent two vertices is important for guaranteeing the existence of these cycles. [Copyright &y& Elsevier]

Abstract: Let be a simple graph on vertices. In this paper, we prove that if satisfies the condition that for each , then has no nowhere-zero 3-flow if and only if is either one of the five graphs on at most 6 vertices or one of a very special class of graphs on at least 6 vertices. [Copyright &y& Elsevier]

Abstract: Let be a -connected graph and be a linear forest in such that and has at most components of order 1, where and . In this paper, we prove that if every independent set of with contains two vertices whose degree sum is at least , then has a cycle of length at least which contains all the vertices and edges of . [Copyright &y& Elsevier]

Abstract: For a graph G, let be the minimum degree sum of an independent set of k vertices. Ore showed that if G is a graph of order with then G is hamiltonian. Let be the connectivity of a graph G. Bauer, Broersma, Li and Veldman proved that if G is a 2-connected graph on n vertices with , then G is hamiltonian. On the other hand, Bondy showed that if G is a 2-connected graph on n vertices with , then each longest cycle of G is a dominating cycle. In this paper, we prove that if G is a 3-connected graph on n vertices with , then G contains a longest cycle which is a dominating cycle. [Copyright &y& Elsevier]

Abstract: Let G be a -connected graph on n vertices. The partially square graph of G is obtained by adding edges whenever the vertices have a common neighbor x satisfying the condition . Clearly , where is the square of G. In particular if G is quasi-claw-free (and claw-free). In this paper we prove that a -connected, graph G is either hamiltonian-connected or the independence number of is at least . As a consequence we answer positively two open questions. The first one by Ainouche and Kouider and the second one by Wu et al. As a by-product we prove that a quasi-claw-free (and hence a claw-free) graph satisfying the condition is hamiltonian-connected. [Copyright &y& Elsevier]

Abstract: Kriesell has proved that every noncomplete -connected graph has a -contractible edge (i.e., an edge whose contraction yields again a -connected graph), if the degree sum of any two vertices with distance at most two is at least . And he guessed that the degree sum condition can be relaxed for only adjacent pairs. In this paper, we verified that is true for . [Copyright &y& Elsevier]

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]

n edge coloring is called vertex-distinguishing if every two distinct vertices are incident to different sets of colored edges. The minimum number of colors required for a vertex-distinguishing proper edge coloring of a simple graph G is denoted by $${\chi'_{vd}(G)}$$. It is proved that $${\chi'_{vd}(G)\leq\Delta(G)+5}$$ if G is a connected graph of order n ≥ 3 and $${\sigma_{2}(G)\geq\frac{2n}{3}}$$, where σ( G) denotes the minimum degree sum of two nonadjacent vertices in G. [ABSTRACT FROM AUTHOR]