The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “Dirac type condition and Hamiltonian graphs”

A note on the Song-Zhang theorem for Hamiltonian graphs

Kewen Zhao, Ronald J. Gould (2010)

Colloquium Mathematicae

Similarity:

An independent set S of a graph G is said to be essential if S has a pair of vertices that are distance two apart in G. In 1994, Song and Zhang proved that if for each independent set S of cardinality k+1, one of the following condition holds: (i) there exist u ≠ v ∈ S such that d(u) + d(v) ≥ n or |N(u) ∩ N(v)| ≥ α (G); (ii) for any distinct u and v in S, |N(u) ∪ N(v)| ≥ n - max{d(x): x ∈ S}, then G is Hamiltonian. We prove that if for each...

Chvátal-Erdös type theorems

Jill R. Faudree, Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson, Colton Magnant (2010)

Discussiones Mathematicae Graph Theory

Similarity:

The Chvátal-Erdös theorems imply that if G is a graph of order n ≥ 3 with κ(G) ≥ α(G), then G is hamiltonian, and if κ(G) > α(G), then G is hamiltonian-connected. We generalize these results by replacing the connectivity and independence number conditions with a weaker minimum degree and independence number condition in the presence of sufficient connectivity. More specifically, it is noted that if G is a graph of order n and k ≥ 2 is a positive integer such that κ(G) ≥ k, δ(G) >...

Improved Sufficient Conditions for Hamiltonian Properties

Jens-P. Bode, Anika Fricke, Arnfried Kemnitz (2015)

Discussiones Mathematicae Graph Theory

Similarity:

In 1980 Bondy [2] proved that a (k+s)-connected graph of order n ≥ 3 is traceable (s = −1) or Hamiltonian (s = 0) or Hamiltonian-connected (s = 1) if the degree sum of every set of k+1 pairwise nonadjacent vertices is at least ((k+1)(n+s−1)+1)/2. It is shown in [1] that one can allow exceptional (k+ 1)-sets violating this condition and still implying the considered Hamiltonian property. In this note we generalize this result for s = −1 and s = 0 and graphs that fulfill a certain connectivity...

On theH-Force Number of Hamiltonian Graphs and Cycle Extendability

Erhard Hexel (2017)

Discussiones Mathematicae Graph Theory

Similarity:

The H-force number h(G) of a hamiltonian graph G is the smallest cardinality of a set A ⊆ V (G) such that each cycle containing all vertices of A is hamiltonian. In this paper a lower and an upper bound of h(G) is given. Such graphs, for which h(G) assumes the lower bound are characterized by a cycle extendability property. The H-force number of hamiltonian graphs which are exactly 2-connected can be calculated by a decomposition formula.

On hyper-Zagreb index conditions for hamiltonicity of graphs

Yong Lu, Qiannan Zhou (2022)

Czechoslovak Mathematical Journal

Similarity:

During the last decade, several research groups have published results on sufficient conditions for the hamiltonicity of graphs by using some topological indices. We mainly study hyper-Zagreb index and some hamiltonian properties. We give some sufficient conditions for graphs to be traceable, hamiltonian or Hamilton-connected in terms of their hyper-Zagreb indices. In addition, we also use the hyper-Zagreb index of the complement of a graph to present a sufficient condition for it to...