Displaying similar documents to “A note on Hamiltonian cycles in generalized Halin graphs”

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.

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...

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...

On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs

Ben Seamone (2015)

Discussiones Mathematicae Graph Theory

Similarity:

A graph is uniquely Hamiltonian if it contains exactly one Hamiltonian cycle. In this note, we prove that claw-free graphs with minimum degree at least 3 are not uniquely Hamiltonian. We also show that this is best possible by exhibiting uniquely Hamiltonian claw-free graphs with minimum degree 2 and arbitrary maximum degree. Finally, we show that a construction due to Entringer and Swart can be modified to construct triangle-free uniquely Hamiltonian graphs with minimum degree 3. ...

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...

New sufficient conditions for hamiltonian and pancyclic graphs

Ingo Schiermeyer, Mariusz Woźniak (2007)

Discussiones Mathematicae Graph Theory

Similarity:

For a graph G of order n we consider the unique partition of its vertex set V(G) = A ∪ B with A = {v ∈ V(G): d(v) ≥ n/2} and B = {v ∈ V(G):d(v) < n/2}. Imposing conditions on the vertices of the set B we obtain new sufficient conditions for hamiltonian and pancyclic graphs.

Dirac type condition and Hamiltonian graphs

Zhao, Kewen (2011)

Serdica Mathematical Journal

Similarity:

2010 Mathematics Subject Classification: 05C38, 05C45. In 1952, Dirac introduced the degree type condition and proved that if G is a connected graph of order n і 3 such that its minimum degree satisfies d(G) і n/2, then G is Hamiltonian. In this paper we investigate a further condition and prove that if G is a connected graph of order n і 3 such that d(G) і (n-2)/2, then G is Hamiltonian or G belongs to four classes of well-structured exceptional graphs.

Cycles in graphs and related problems

Antoni Marczyk

Similarity:

Our aim is to survey results in graph theory centered around four themes: hamiltonian graphs, pancyclic graphs, cycles through vertices and the cycle structure in a graph. We focus on problems related to the closure result of Bondy and Chvátal, which is a common generalization of two fundamental theorems due to Dirac and Ore. We also describe a number of proof techniques in this domain. Aside from the closure operation we give some applications of Ramsey theory in the research of cycle...

On Vertices Enforcing a Hamiltonian Cycle

Igor Fabrici, Erhard Hexel, Stanislav Jendrol’ (2013)

Discussiones Mathematicae Graph Theory

Similarity:

A nonempty vertex set X ⊆ V (G) of a hamiltonian graph G is called an H-force set of G if every X-cycle of G (i.e. a cycle of G containing all vertices of X) is hamiltonian. The H-force number h(G) of a graph G is defined to be the smallest cardinality of an H-force set of G. In the paper the study of this parameter is introduced and its value or a lower bound for outerplanar graphs, planar graphs, k-connected graphs and prisms over graphs is determined.

Chvátal-Erdos condition and pancyclism

Evelyne Flandrin, Hao Li, Antoni Marczyk, Ingo Schiermeyer, Mariusz Woźniak (2006)

Discussiones Mathematicae Graph Theory

Similarity:

The well-known Chvátal-Erdős theorem states that if the stability number α of a graph G is not greater than its connectivity then G is hamiltonian. In 1974 Erdős showed that if, additionally, the order of the graph is sufficiently large with respect to α, then G is pancyclic. His proof is based on the properties of cycle-complete graph Ramsey numbers. In this paper we show that a similar result can be easily proved by applying only classical Ramsey numbers.