In [Graphs Combin. 24 (2008) 469-483], the third author and the fifth author conjectured that if G is a k-connected graph such that sigma(k+1)(G) >= vertical bar V (G)vertical bar + kappa(G) + (k - 2) (alpha(G) - 1), then G contains a Hamilton cycle, where sigma(k+1)(G), kappa(G) and alpha(G) are the minimum degree sum of k+1 independent vertices, the connectivity and the independence number of G, respectively. In this paper, we settle this conjecture. The degree sum condition is best possible.

In this paper, we give the following result: If D is a digraph of order n, and if d+D(u) + d−D(v) ≥ n for every two distinct vertices u and v with (u, v) ∈/ A(D), then D has a directed 2-factor with exactly k directed cycles of length at least 3, where n ≥ 12k+3. This result is equivalent to the following result: If G is a balanced bipartite graph of order 2n with partite sets X and Y , and if dG(x) + dG(y) ≥ n + 2 for every two vertices x ∈ X and y ∈ Y with xy ∈/ E(G), then for every perfect matching M, G has a 2-factor with exactly k cycles of length at least 6 containing every edge of M, where n ≥ 12k + 3. These results are generalizations of theorems concerning Hamilton cycles due to Woodall [Proc. Lond. Math. Soc., 24 (1972), pp. 739–755] and Las Vergnas [Problémes de couplages et problémes hamiltoniens en théorie des graphes, Ph.D. thesis, University of Paris, 1972], respectively.

In this paper, we survey results and conjectures on degree conditions for the existence of vertex-disjoint cycles and paths. In particular, we focus on the type of degree conditions, the type of cycles or paths, and relations between results or conjectures.

Let G be a balanced bipartite graph of order 2n >= 4, and let sigma(1,1)(G) be the minimum degree sum of two non-adjacent vertices in different partite sets of G. In 1963, Moon and Moser proved that if sigma(1,1)(G) >= n + 1, then G is hamiltonian. In this note, we show that if k is a positive integer, then the Moon Moser condition also implies the existence of a 2-factor with exactly k cycles for sufficiently large graphs. In order to prove this, we also give a sigma(1,1) condition for the existence of k vertex-disjoint alternating cycles with respect to a chosen perfect matching in G. (C) 2017 Elsevier B.V. All rights reserved.

Let k be a positive integer, and let G be a graph of order n >= 3k and S be a set of k vertices of G. In this paper, we prove that if sigma(2)(G) > n + k - 1 + Delta(G[S]), then G can be partitioned into k vertex-disjoint cycles C1, Ck i, Ck such that vertical bar V(C-i) boolean AND S] = 1 for 1 <= i <= k, and vertical bar V(C-i)vertical bar = 3 for 1 <= i <= k - Delta(G[5]) and vertical bar V(C-i)vertical bar <= 4 for k - Delta(G[S]) <= i <= k - 1, where sigma(2)(G) denotes the minimum degree sum of two non-adjacent vertices in G and Delta(G[S]) denotes the maximum degree of the subgraph of G induced by S. This is a common generalization of the results obtained by Dong (2010) and Chiba et al. (2010), respectively. In order to show the main theorem, we further give other related results concerning the degree conditions for the existence of k vertex-disjoint cycles in which each cycle contains a vertex in a specified vertex subset. (C) 2016 Elsevier B.V. All rights reserved.

Let G be a graph, and let S be a subset of the vertex set of G. We denote the set of the end vertices of a path P by end(P). A path P is an S-path if vertical bar V(P)vertical bar >= 2 and V(P) boolean AND S = end(P). An S-path-system is a graph H such that H contains all vertices of S and every component of H is an S-path. In this paper, we give a sharp degree sum condition for a bipartite graph to have a spanning S-path-system. (C) 2016 Elsevier B.V. All rights reserved.

Aldred and Plummer (1999) have proved that every m-connected K-1,K-m-k+2-free graph of even order contains a perfect matching which avoids k prescribed edges. They have also proved that the result is best possible in the range 1 <= k <= 1/2(m + 1). In this paper, we show that if 1/2(m + 2) <= k <= m - 1, their result is not best possible. We prove that if m >= 4 and 1/2(m + 2) <= k <= m - 1, every K-1,K-[2m-k+4/3]-free graph of even order contains a perfect matching which avoids k prescribed edges. While this is a best possible result in terms of the order of a forbidden star, if 2m - k + 4 equivalent to 0 (mod 3), we also prove that only finitely many sharpness examples exist. (C) 2015 Elsevier B.V. All rights reserved.

A tree is called a k-tree if its maximum degree is at most k. We prove the following theorem. Let k >= 2 be an integer, and G he a connected bipartite graph with bipartition (A, B) such that |A| <= |B| <= (k - 1) |A| + 1. If sigma(k)(G) >= |B|, then G has a spanning k-tree, where sigma(k)(G) denotes the minimum degree sum of k independent vertices of G. Moreover, the condition on sigma(k) (G) is sharp. It was shown by Win (Abh. Math. Sem. Univ. Hamburg, 43, 263-267, 1975) that if a connected graph H satisfies sigma(k)(H) >= |H| - 1, then H has a spanning k-tree. Thus our theorem shows that the condition becomes much weaker if the graph is bipartite.

We denote the order, the independence number, the connectivity and the minimum degree sum of independent four vertices of a graph G by n(G), alpha(G), K(G) and sigma(4)(G), respectively. The circumference of a graph G, denoted by c(G), is the length of a longest cycle in G. We call a cycle C of a graph G a D-k-cycle if the order of each component of G - V(C) is at most k - 1. Our goal is to accomplish the proof of the statement that if G is a 4-connected graph, then c(G) >= min{sigma(4)(G) - K(G) - alpha(G) + 1, n(G)}. In order to prove this, we consider three conditions for the construction of the outside of a longest cycle: (i) If G is a 3-connected graph and every longest cycle of G is a D-2-cycle, then c(G) >= min{sigma(4)(G) - K(G) - alpha(G) +1, n (G)} (ii) If G is a 3-connected graph and every longest cycle is a D-3-cycle and some longest cycle is not a D-2-cycle, then c(G) >= sigma(4)(G) - K(G) - 4. (iii) If G is a 4-connected graph and some longest cycle is not a D-3-cycle, then c(G) >= sigma(4)(G) - 8. For each condition, the lower bound of the circumference is sharp. (C) 2014 Elsevier B.V. All rights reserved.

In this paper, we propose a new closure concept for spanning k-trees. A k-tree is a tree with maximum degree at most k. We prove that: Let G be a connected graph and let u and v be nonadjacent vertices of G. Suppose that for every independent set S in G of order k with . Then G has a spanning k-tree if and only if G + uv has a spanning k-tree. This result implies Win's result (Abh Math Sem Univ Hamburg, 43:263-267, 1975) and Kano and Kishimoto's result (Graph Comb, 2013) as corollaries.

Let k be a non-negative integer. A branch vertex of a tree is a vertex of degree at least three. We show two sufficient conditions for a connected claw-free graph to have a spanning tree with a bounded number of branch vertices: (i) A connected claw-free graph has a spanning tree with at most k branch vertices if its independence number is at most 2k + 2. (ii) A connected claw-free graph of order n has a spanning tree with at most one branch vertex if the degree sum of any five independent vertices is at least n - 2. These conditions are best possible. A related conjecture also is proposed.

We denote by G[X, Y] a bipartite graph G with partite sets X and Y. Let d (G) (v) be the degree of a vertex v in a graph G. For G[X, Y] and we define . Amar et al. (Opusc. Math. 29:345-364, 2009) obtained sigma (1,1)(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| a parts per thousand yen |Y| and such that sigma (1,1)(S) a parts per thousand yen |X| + 1, then either there exists a cycle containing S or and there exists a cycle containing Y. This degree sum condition is sharp.

A tree is called a caterpillar if all its leaves are adjacent to the same its path, and the path is called a spine of the caterpillar. Broersma and Tuinstra proved that if a connected graph G satisfies σ2(G) ≥ |G| - k + 1 for an integer k ≥ 2, then G has a spanning tree having at most k leaves. In this paper we improve this result as follows. If a connected graph G satisfies σ2(G) ≥ |G| - k + 1 and |G| ≥ 3k - 10 for an integer k ≥ 2, then G has a spanning caterpillar having at most k leaves. Moreover, if |G| ≥ 3k - 7, then for any longest path, G has a spanning caterpillar having at most k leaves such that its spine is the longest path. These three lower bounds on σ2(G) and |G| are sharp. © 2013 Springer-Verlag.

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 kappa(G) be the connectivity of G, and let sigma (3)(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) a parts per thousand yen 2, then either (i) c(G) a parts per thousand yen sigma (3)(G) - 3 or (ii) kappa(G) = 2 and p(G) a parts per thousand yen sigma (3)(G) - 1. This result implies several known results as corollaries and gives a new lower bound of the circumference.

Let G vertical bar X, Y vertical bar be a 2-connected bipartite graph with vertical bar X vertical bar >= vertical bar Y vertical bar. For S subset of V(G), we define delta(S; G) := min{d(G)(nu) : nu is an element of S}. We define sigma(1,1)(G) := min {d(G)(x) + d(G)(y) : x is an element of X, y is an element of Y. xy is not an element of E(G)} and sigma(2)(X) := min{d(G)(x) + d(G)(y) : x, y is an element of X, x not equal y}. We denote by c(G) the length of a longest cycle in G. Jackson [B. Jackson, Long cycles in bipartite graphs, J. Combin. Theory Ser. B 38 (1985) 118-131] proved that c(G) >= min{2 delta(X; G) + 2 delta(Y; G) - 2, 4 delta(X; G) - 4, 2 vertical bar Y vertical bar}. In this paper, we extend this result, and prove that c(G) >= min{2 sigma(1,1)(G) - 2, 2 sigma(2)(X) - 4, 2 vertical bar Y vertical bar}. (C) 2012 Elsevier B.V. All rights reserved.

For a graph H and an integer k >= 2, let sigma(k)(H) denote the minimum degree sum of k independent vertices of H. We prove that if a connected claw-free graph G satisfies sigma(k+1)(G) >= vertical bar G vertical bar - k, then G has a spanning tree with at most k leaves. We also show that the bound vertical bar G vertical bar - k is sharp and discuss the maximum degree of the required spanning trees.

In this paper, we give a survey of spanning trees. We mainly deal with spanning trees having some particular properties concerning a hamiltonian properties, for example, spanning trees with bounded degree, with bounded number of leaves, or with bounded number of branch vertices. Moreover, we also study spanning trees with some other properties, motivated from optimization aspects or application for some problems.

A cycle C in a graph G is said to be dominating if E(G - C) = empty set. Enomoto et al. showed that if G is a 2-connected triangle-free graph with alpha(G) <= 2 kappa(G) - 2, then every longest cycle is dominating. But it is unknown whether the condition on the independence number is sharp. In this paper, we show that if G is a 2-connected triangle-free graph with alpha(G) <= 2 kappa(G) - 1, then G has a longest cycle which is dominating. This condition is best possible.

In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n >= 1, k >= 3, c >= 0 and G be an n-connected graph. Suppose that for every independent set S. V( G) of cardinality n( k - 1) + c + 2, there exists a vertex set X. S of cardinality k such that the degree sum of vertices in X is at least |V(G)| - c - 1. Then G has a spanning tree T with maximum degree at most k + [c/n] and Sigma(v is an element of V(T)) max{d(T) (v) - k, 0} <= c.

Let G be a connected graph, let X subset of V (G) and let f be a mapping from X to {2, 3, ...}. Kaneko and Yoshimoto (Inf Process Lett 73: 163-165, 2000) conjectured that if vertical bar N(G) (S) - X vertical bar >= f (S) - 2 vertical bar S vertical bar + omega(G)(S) + 1 for any subset S subset of X, then there exists a spanning tree T such that d(T) (x) >= f (x) for all x is an element of X. In this paper, we show a result with a stronger assumption than this conjecture; if vertical bar N(G)(S) - X vertical bar >= f (S) - 2 vertical bar S vertical bar + alpha (S) + 1 for any subset S subset of X, then there exists a spanning tree T such that d(T) (x) >= f (x) for all x is an element of X.

For a graph G, p(G) and c(G) denote the orders of a longest path and a longest cycle of G. respectively. For a graph G, we denote by d(G)(x) and K(G) the degree of a vertex x in G and the connectivity of G, respectively. In this paper, we prove that if G is a 3-connected graph of order n such that Sigma(4)(i=1) d(G)(x(i)) >= n + k (G) + 3 for every independent set {x(1), x(2), x(3), x(4)}, then p(G) - c(G) <= 1. 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. (C) 2009 Elsevier B.V. All rights reserved.

For a graph G, p(G) and c(G) denote the order of a longest path and a longest cycle of G, respectively. In this paper, we prove that if G is a 3-connected graph of order n such that the minimum degree sum of four independent vertices is at least n + 6, then p(G) - c(G) <= 2. By considering our result and the results in [J Graph Theory 20 (1995), 213-225; Amer Math Monthly 67 (1950), 55], we propose a conjecture which is a generalization of Bondy's conjecture. Furthermore, using our result, for a graph satisfying the above conditions, we obtain a new lower bound of the circumference and establish Thomassen's conjecture.(C) 2009 Wiley Periodicals, Inc. J Graph Theory 62: 279-291, 2009

Let G be a graph and let sigma(k)(G) be the minimum degree sum of an independent set of k vertices. For S subset of V(G) with vertical bar S vertical bar >= k, let Delta(k)(S) denote the maximum value among the degree sums of the subset of k vertices in S. A cycle C of a graph G is said to be a dominating cycle if V(G \ C) is an independent set. In [2], Bondy showed that if G is a 2-connected graph with sigma(3) (G) >= vertical bar V(G)vertical bar + 2, then any longest cycle of G is a dominating cycle. In this paper, we improve it as follows: if G is a 2-connected graph with Delta(3)(S) >= vertical bar V(G)vertical bar + 2 for every independent set S of order kappa(G) + 1, then any longest cycle of G is a dominating cycle.

Let G be an (in + 2)-graph on it vertices, and F be a linear forest in G with |E(F)| = in and cut (F) = s, where omega(1) (F) is the number of components of order one in F. We denote by sigma(3)(G) the minimum value of the degree sum of three vertices which are pairwise non-adjacent. In this paper, we give several sigma(3) conditions for a dominating cycle or a hamiltonian cycle passing through a linear forest. We first prove that if sigma(3)(G) >= n + 2m + 2 + max{s - 3, 0}, then every longest cycle passing through F is dominating. Using this result, we prove that if sigma(3)(G) >= n + k(G) + 2m -1 then G contains a hamiltonian cycle passing through F. As a corollary, we obtain a result that if G is a 3-connected graph and sigma(3)(G) >= n + k(G) + 2, then G is hamiltonian-connected. (C) 2008 Elsevier B.V. All rights reserved.

For a graph G, p(G) and c(G) denote the order of a longest path and a longest cycle of G, respectively. Bondy and Locke [J.A. Bondy, S.C. Locke, Relative length of paths and cycles in 3-connected graphs, Discrete Math. 33 (1981) 111-122] consider the gap between p(G) and c(G) in 3-connected graphs G. Starting with this result, there are many results appeared in this context, see [H. Enomoto, J. van dell Heuvel, A. Kaneko, A. Saito, Relative length of long paths and cycles in graphs with large degree sums, J. Graph Theory 20 (1995) 213-225; M. Lu, H. Liu, F Tian, Relative length of longest paths and cycles in graphs, Graphs Combin. 23 (2007) 433-443; K. Ozeki, M. Tsugaki, T Yamashita, Oil relative length of longest paths and cycles, preprint; I. Schiermeyer, M. Tewes, Longest paths and longest cycles in graphs with large degree Slims, Graphs Combin. 18 (2002) 633-643]. In this paper, we investigate graphs G with p(G) - c(G) at most I or at most 2, but with no hamiltonian paths. Let G be a 2-connected graph of order n, which has no hamiltonian paths. We show two results as follows: (i) if sigma(4)(G) >= 1/3 (4n - 2), then p(G) - c(G) <= 1, and (ii) if sigma(4)(G) >= n + 3, then p(G) - c(G) <= 2.C) 2007 Elsevier B.V. All rights reserved.

Let G be a graph. For S subset of V(G), let Delta(k) (S) denote the maximum value of the degree sums of the subsets of S of order k. In this paper, we prove the following two results. (1) Let G be a 2-connected graph. If Delta(2) (S) >= d for every independent set S of order kappa(G) + 1, then G has a cycle of length at least min{d, |V(G)|}. (2) Let G be a 2-connected graph and X a subset of V(G). If Delta(2)(S) >= |V(G)| for every independent set S of order kappa(X) + 1 in G|X|, then G has a cycle that includes every vertex of X. This suggests that the degree sum of nonadjacent two vertices is important for guaranteeing the existence of these cycles. (C) 2007 Elsevier B.V. All rights reserved.

Let G be a graph and S. V(G). We denote by a(S) the maximum number of pairwise nonadjacent vertices in S. For x, y epsilon V(G), the local connectivity kappa(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 epsilon S, x not equal y}. In this paper, we show that if kappa(S) >= 3 and Sigma(4)(i=1) dG(x(i)) >= | V(G)|+ kappa(S)+ alpha(S) - 1 for every independent set {x(1), x(2), x(3), x(4)} subset of 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.

Let G be a (k + m)-connected graph and F be a linear forest in G such that vertical bar E(F)vertical bar = m and F has at most k - 2 components of order 1, where k >= 2 and m >= 0. In this paper, we prove that if every independent set S of G with vertical bar S vertical bar = k + 1 contains two vertices whose degree sum is at least d, then G has a cycle C of length at least min {d - m, vertical bar V(G)vertical bar} which contains all the vertices and edges of F. (C) 2007 Elsevier B.V. All rights reserved.

In this article, we prove the following theorem. Let k >= 3 be an integer, G be a k-connected graph with minimum degree d and X be a set of k + 1 vertices on a cycle. Then G has a cycle of length at least min{2d, vertical bar V(G)vertical bar} passing through X This result gives the positive answer to the Question posed by Locke [8]. (C) 2008 Wiley Periodicals, Inc.

Ore presented a degree condition involving every pair of nonadjacent vertices for a graph to be hamiltonian. Fan [New sufficient conditions for cycles in graphs, J. Combin. Theory Ser. B 37 (1984) 221-227] showed that not all the pairs of nonadjacent vertices are required, but only the pairs of vertices at the distance two suffice. Bedrossian et al. [A generalization of Fan's condition for harniltonicity, pancyclicity, and hamiltonian connectedness, Discrete Math. 115 (1993) 39-50] improved Fan's result involving the pairs of vertices contained in an induced claw or an induced modified claw. On the other hand, Matthews and Sumner [Longest paths and cycles in K-1,K-3-free graphs, J. Graph Theory 9 (1985) 269-277] gave a minimum degree condition for a claw-free graph to be hamiltonian. In this paper, we give a new degree condition in an induced claw or an induced modified claw ensuring the hamiltonicity of graphs which extends both results of Bederossian et al. and Matthews and Sumner. (c) 2007 Elsevier B.V. All rights reserved.

For a graph G, let sigma(k) (G) be the minimum degree sum of an independent set of k vertices. Ore showed that if G is a graph of order n >= 3 with sigma(2) (G) >= n then G is hamiltonian. Let kappa(G) 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 sigma(3) (G) >= n + kappa(G), then G is hamiltonian. On the other hand, Bondy showed that if G is a 2-connected graph on n vertices with 93 (G) >= n + 2, 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 sigma(4) (G) >= n + kappa(G) + 3, then G contains a longest cycle which is a dominating cycle. (c) 2007 Elsevier B.V. All rights reserved.

Let k >= 2 be an integer. We show that if G is a (k + 1)-connected graph and each pair of nonadjacent vertices in G has degree sum at least vertical bar G vertical bar + 1, then for each subset S of V(G) with vertical bar S vertical bar = k, G has a spanning tree such that S is the set of endvertices. This result generalizes Ore's theorem which guarantees the existence of a Hamilton path connecting any two vertices.

A set S of vertices in a graph G is said to be an edge-dominating set if every edge in G is incident with a vertex in S. A cycle in G is said to be a dominating cycle if its vertex set is an edge-dominating set. Nash-Williams [Edge-disjoint hamiltonian circuits in graphs with vertices of large valency, Studies in Pure Mathematics, Academic Press, London, 1971, pp. 157-183] has proved that every longest cycle in a 2-connected graph of order n and minimum degree at least 1/3(n + 2) is a dominating cycle. In this paper, we prove that for a prescribed positive integer k, under the same minimum degree condition, if n is sufficiently large and if we take k disjoint cycles so that they contain as many vertices as possible, then these cycles form an edge-dominating set. Nash-Williams' Theorem corresponds to the case of k = 1 of this result. (C) 2007 Elsevier B.V. All rights reserved.

In this paper, we prove that an m-connected graph G on n vertices has a spanning tree with at most k leaves (for k >= 2 and m >= 1) if every independent set of G with cardinality m + k contains at least one pair of vertices with degree sum at least n -k + 1. This is a common generalization of results due to Broersma and Tuinstra and to Win.

For a graph G, we denote by d(G)(x) and kappa(G) the degree of a vertex x in G and the connectivity of G, respectively. In this article, we show that if G is a 3-connected graph of order n such that d(G)(x) + d(G)(y) + d(G)(z) >= for every independent set {x, y, z}, then G contains a cycle of length least min{d - kappa(G), n}. (C) 2006 Wiley Periodicals, Inc.

Let G be a graph and let f be a non-negative integer-valued function defined on V(G). Then a cycle C is called an f-dominating cycle if d(G)(v, C) less than or equal to f (v) holds for each v is an element of V(G), where d(G)(v,C) denotes the distance between v and C. A set S is called an f-stable set if d(G)(u, v) greater than or equal to f (u) + f (v) holds for each pair of distinct vertices u, v in S, and denote by alpha(f)(G) the order of a largest f-stable set in G. In this paper, we prove that if a k-connected graph G (k greater than or equal to 2) satisfies alpha(f+1)(G) less than or equal to k, then G has an f-dominating cycle, where f + 1 is the function defined by (f + 1)(v) = f (v) + 1. By taking an appropriate function as f, we can deduce a number of known results from this theorem. (C) 2003 Elsevier B.V. All rights reserved.

A cycle C in a graph G is said to be a dominating cycle if every vertex of G has a neighbor on C. Strengthening a result of Bondy and Fan [3] for tough graphs, we prove that a k-connected graph G (k greater than or equal to 2) of order p with t(G) > k/(k + 1) has a dominating cycle if Sigma(xis an element ofS) deg(G) x greater than or equal to p-2k-2 for each S subset of V(G) of order k + 1 in which every pair of vertices in S have distance at least four in G.