Displaying similar documents to “Hamiltonian-connected graphs and their strong closures.”

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

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

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.

A New Proof that 4-Connected Planar Graphs are Hamiltonian-Connected

Xiaoyun Lu, Douglas B. West (2016)

Discussiones Mathematicae Graph Theory

Similarity:

We prove a theorem guaranteeing special paths of faces in 2-connected plane graphs. As a corollary, we obtain a new proof of Thomassen’s theorem that every 4-connected planar graph is Hamiltonian-connected.

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.

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

Heavy Subgraphs, Stability and Hamiltonicity

Binlong Li, Bo Ning (2017)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph. Adopting the terminology of Broersma et al. and Čada, respectively, we say that G is 2-heavy if every induced claw (K1,3) of G contains two end-vertices each one has degree at least |V (G)|/2; and G is o-heavy if every induced claw of G contains two end-vertices with degree sum at least |V (G)| in G. In this paper, we introduce a new concept, and say that G is S-c-heavy if for a given graph S and every induced subgraph G′ of G isomorphic to S and every maximal clique...