Search

For a 2-connected graph G , the relative length of G , denoted by diff (G) , is the difference between the orders of a longest path and a longest cycle in G. This parameter is used as a measure to estimate how close a given graph is to a hamiltonian graph. Let σ k (G) be the least value of the sums of degrees of vertices in independent sets of cardinality k. In 2008, Paulusma and Yoshimoto proved that a 2-connected triangle-free graph G of order n with σ 4 (G) ≥ n + 2 satisfies diff (G) ≤ 1 unless G is isomorphic to one exceptional graph G 0. In this paper, we extend their result and prove that for an integer s with 2 3 (n + 4) < s ≤ n + 2 , a 2-connected triangle-free graph of order n with σ 4 (G) ≥ s satisfies diff (G) ≤ n + 3 − s unless s = σ 4 (G) = n + 2 and G = G 0. [ABSTRACT FROM AUTHOR]

Abstract: We consider 2-factors with a bounded number of components in the -times iterated line graph . We first give a characterization of graph such that has a 2-factor containing at most components, based on the existence of a certain type of subgraph in . This generalizes the main result of [L. Xiong, Z. Liu, Hamiltonian iterated line graphs, Discrete Math. 256 (2002) 407–422]. We use this result to show that the minimum number of components of 2-factors in the iterated line graphs is stable under the closure operation on a claw-free graph . This extends results in [Z. Ryjáček, On a closure concept in claw-free graphs, J. Combin. Theory Ser. B 70 (1997) 217–224; Z. Ryjáček, A. Saito, R.H. Schelp, Closure, 2-factors and cycle coverings in claw-free graphs, J. Graph Theory 32 (1999) 109–117; L. Xiong, Z. Ryjáček, H.J. Broersma, On stability of the hamiltonian index under contractions and closures, J. Graph Theory 49 (2005) 104–115]. [Copyright &y& Elsevier]

Let G=(X,Y) be a 2-connected balanced bipartite graph with |X|=|Y|=n. In this paper, we prove that if |N(x1)∪N(x2)|+|N(y1)∪N(y2)|⩾n+2 for any {x1,x2}⊆X and {y1,y2}⊆Y, then G is hamiltonian except when G is a special graph on 8 or on 12 vertices. [Copyright &y& Elsevier]

Abstract: Let be a graph of order . An even squared Hamiltonian cycle (ESHC) of is a Hamiltonian cycle of with chords for all (where for ). When is even, an ESHC contains all bipartite -regular graphs of order . We prove that there is a positive integer such that for every graph of even order , if the minimum degree is , then contains an ESHC. We show that the condition of being even cannot be dropped and the constant cannot be replaced by . Our results can be easily extended to even th powered Hamiltonian cycles for all . [Copyright &y& Elsevier]

Abstract: In 1960 Ore proved the following theorem: Let G be a graph of order n. If for every pair of nonadjacent vertices u and , then G is hamiltonian. In this note we strengthen Ore''s theorem as follows: we determine the maximum number of pairs of nonadjacent vertices that can have degree sum less than n (i.e. violate Ore''s condition) but still imply that the graph is hamiltonian. Some other sufficient conditions (i.e. Fan''s condition) for hamiltonian graphs are strengthened as well. [Copyright &y& Elsevier]

The Chva´tal-Erdo˝s theorem says that a 2-connected graph with α(G)&les;κ(G) is hamiltonian. We extend this theorem for triangle-free graphs. We prove that if G is a 2-connected triangle-free graph of order n with α(G)&les;2κ(G)−2, then every longest cycle in G is dominating, and G has a cycle of length at least min{n−α(G)+κ(G),n}. [Copyright &y& Elsevier]

Abstract: For an integer with and a pair of connected graphs and of order at least three, we say that is a -forbidden pair if every -connected -free graph, except possibly for a finite number of exceptions, is Hamiltonian. If no exception arises, is said to be a strong -forbidden pair. The 2-forbidden pairs and the strong 2-forbidden pairs are determined by Faudree and Gould (1997) and Bedrossian (1991) , respectively. All of them contain . In this paper, we prove that is a strong -forbidden pair, which shows that is not always necessary in a -forbidden pair for . On the other hand, we prove that each -forbidden pair contains for some . We also discuss several other Hamiltonian properties of -connected -free graphs. [Copyright &y& Elsevier]

Abstract: In this paper we generalize a Theorem of Jung which shows that 1-tough graphs with are hamiltonian. Our generalization shows that these graphs contain a wide variety of 2-factors. In fact, these graphs contain not only 2-factors having just one cycle (the hamiltonian case) but 2-factors with cycles, for any such that . [Copyright &y& Elsevier]

The classical Ore's Theorem states that every graph G of order n ≥ 3 with σ 2 (G) ≥ n is hamiltonian, where σ 2 (G) = min { d G (x) + d G (y) : x , y ∈ V (G) , x ≠ y , x y ∉ E (G) }. Recently, Ferrara, Jacobson and Powell (Discrete Math. 312 (2012), 459–461) extended the Moon–Moser Theorem and characterized the non-hamiltonian balanced bipartite graphs H of order 2 n ≥ 4 with partite sets X and Y satisfying σ 1 , 1 (H) ≥ n , where σ 1 , 1 (H) = min { d H (x) + d H (y) : x ∈ X , y ∈ Y , x y ∉ E (H) }. Though the latter result apparently deals with a narrower class of graphs, we prove in this paper that it implies Ore's Theorem for graphs of even order. [ABSTRACT FROM AUTHOR]