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:
Michal Tkáč, Heinz-Jürgen Voss (2002)
Discussiones Mathematicae Graph Theory
Similarity:
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.
Magdalena Bojarska (2010)
Discussiones Mathematicae Graph Theory
Similarity:
We show that every 2-connected (2)-Halin graph is Hamiltonian.
Moshe Rosenfeld (1989)
Aequationes mathematicae
Similarity:
Linda M. Lesniak (1978)
Aequationes mathematicae
Similarity:
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. ...
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...
W.T. Tutte (1977)
Aequationes 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...
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.
Z. Skupień (1989)
Banach Center Publications
Similarity:
Ronald J. Gould (1981)
Colloquium 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.
Carsten Thomassen (1973)
Mathematische Annalen
Similarity:
Peter J. Owens, Hansjoachim Walther (1995)
Discussiones Mathematicae Graph Theory
Similarity:
The family of 5-valent polyhedral graphs whose faces are all triangles or 3s-gons, s ≥ 9, is shown to contain non-hamiltonian graphs and to have a shortness exponent smaller than one.