Displaying similar documents to “Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs”

A classification for maximal nonhamiltonian Burkard-Hammer graphs

Ngo Dac Tan, Chawalit Iamjaroen (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G = (V,E) is called a split graph if there exists a partition V = I∪K such that the subgraphs G[I] and G[K] of G induced by I and K are empty and complete graphs, respectively. In 1980, Burkard and Hammer gave a necessary condition for a split graph G with |I| < |K| to be hamiltonian. We will call a split graph G with |I| < |K| satisfying this condition a Burkard-Hammer graph. Further, a split graph G is called a maximal nonhamiltonian split graph if G is nonhamiltonian...

The Ryjáček Closure and a Forbidden Subgraph

Akira Saito, Liming Xiong (2016)

Discussiones Mathematicae Graph Theory

Similarity:

The Ryjáček closure is a powerful tool in the study of Hamiltonian properties of claw-free graphs. Because of its usefulness, we may hope to use it in the classes of graphs defined by another forbidden subgraph. In this note, we give a negative answer to this hope, and show that the claw is the only forbidden subgraph that produces non-trivial results on Hamiltonicity by the use of the Ryjáček closure.

Hamilton cycles in almost distance-hereditary graphs

Bing Chen, Bo Ning (2016)

Open Mathematics

Similarity:

Let G be a graph on n ≥ 3 vertices. A graph G is almost distance-hereditary if each connected induced subgraph H of G has the property dH(x, y) ≤ dG(x, y) + 1 for any pair of vertices x, y ∈ V(H). Adopting the terminology introduced by Broersma et al. and Čada, a graph G is called 1-heavy if at least one of the end vertices of each induced subgraph of G isomorphic to K1,3 (a claw) has degree at least n/2, and is called claw-heavy if each claw of G has a pair of end vertices with degree...

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

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.

Hamilton cycles in split graphs with large minimum degree

Ngo Dac Tan, Le Xuan Hung (2004)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G is called a split graph if the vertex-set V of G can be partitioned into two subsets V₁ and V₂ such that the subgraphs of G induced by V₁ and V₂ are empty and complete, respectively. In this paper, we characterize hamiltonian graphs in the class of split graphs with minimum degree δ at least |V₁| - 2.