On Hamiltonian properties of powers of special Hamiltonian graphs
Gary Chartrand, S. F. Kapoor (1974)
Colloquium Mathematicae
Similarity:
Gary Chartrand, S. F. Kapoor (1974)
Colloquium Mathematicae
Similarity:
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...
Magdalena Bojarska (2010)
Discussiones Mathematicae Graph Theory
Similarity:
We show that every 2-connected (2)-Halin graph is Hamiltonian.
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.
Z. Skupień (1989)
Banach Center Publications
Similarity:
Ronald J. Gould (1981)
Colloquium Mathematicae
Similarity:
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...
Linda M. Lesniak (1978)
Aequationes mathematicae
Similarity:
Michal Tkáč, Heinz-Jürgen Voss (2002)
Discussiones Mathematicae Graph Theory
Similarity:
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.
Bohdan Zelinka (1998)
Discussiones Mathematicae Graph Theory
Similarity:
Two classes of graphs which are maximal with respect to the absence of Hamiltonian paths are presented. Block graphs with this property are characterized.
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.
Moshe Rosenfeld (1989)
Aequationes mathematicae
Similarity:
Jerzy A. Filar, Michael Haythorpe, Giang T. Nguyen (2010)
Discussiones Mathematicae Graph Theory
Similarity:
Almost all d-regular graphs are Hamiltonian, for d ≥ 3 [8]. In this note we conjecture that in a similar, yet somewhat different, sense almost all cubic non-Hamiltonian graphs are bridge graphs, and present supporting empirical results for this prevalence of the latter among all connected cubic non-Hamiltonian graphs.
Zdzisław Skupień (1966)
Fundamenta Mathematicae
Similarity:
Z. Skupień (1974)
Colloquium Mathematicae
Similarity:
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.