Displaying similar documents to “Pairs of edge disjoint Hamiltonian circuits in 5-connected planar graphs.”

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

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

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.