A note on Hamiltonian cycles in generalized Halin graphs
Magdalena Bojarska (2010)
Discussiones Mathematicae Graph Theory
Similarity:
We show that every 2-connected (2)-Halin graph is Hamiltonian.
Magdalena Bojarska (2010)
Discussiones Mathematicae Graph Theory
Similarity:
We show that every 2-connected (2)-Halin graph is Hamiltonian.
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.
Z. Skupień (1989)
Banach Center Publications
Similarity:
Fan Wang, Weisheng Zhao (2018)
Discussiones Mathematicae Graph Theory
Similarity:
Ruskey and Savage asked the following question: Does every matching in a hypercube Qn for n ≥ 2 extend to a Hamiltonian cycle of Qn? Fink confirmed that every perfect matching can be extended to a Hamiltonian cycle of Qn, thus solved Kreweras’ conjecture. Also, Fink pointed out that every matching can be extended to a Hamiltonian cycle of Qn for n ∈ {2, 3, 4}. In this paper, we prove that every matching in Q5 can be extended to a Hamiltonian cycle of Q5.
Ralph Faudree, Odile Favaron, Evelyne Flandrin, Hao Li (1996)
Discussiones Mathematicae Graph Theory
Similarity:
We first show that if a graph G of order n contains a hamiltonian path connecting two nonadjacent vertices u and v such that d(u)+d(v) ≥ n, then G is pancyclic. By using this result, we prove that if G is hamiltonian with order n ≥ 20 and if G has two nonadjacent vertices u and v such that d(u)+d(v) ≥ n+z, where z = 0 when n is odd and z = 1 otherwise, then G contains a cycle of length m for each 3 ≤ m ≤ max (dC(u,v)+1, [(n+19)/13]), being the distance of u and v on a hamiltonian cycle...
D. Z. Du, D. F. Hsu (1989)
Banach Center Publications
Similarity:
Ordaz, Oscar, González, Leida, Márquez, Isabel, Quiroz, Domingo (2000)
Divulgaciones Matemáticas
Similarity:
Blain, Paul, Bowlin, Garry, Foisy, Joel, Hendricks, Jacob, LaCombe, Jason (2007)
The New York Journal of Mathematics [electronic only]
Similarity:
Tudor Zamfirescu (1971)
Rendiconti del Seminario Matematico della Università di Padova
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...
Gary Chartrand, S. F. Kapoor (1974)
Colloquium Mathematicae
Similarity:
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.
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...
Fleischner, H., Horák, P., Širáň, J. (1993)
Acta Mathematica Universitatis Comenianae. New Series
Similarity:
Ronald J. Gould (1981)
Colloquium Mathematicae
Similarity:
Hopkins, Brian (2004)
International Journal of Mathematics and Mathematical Sciences
Similarity: