Degree sets for homogeneously traceable non-Hamiltonian graphs
Ronald J. Gould (1981)
Colloquium Mathematicae
Similarity:
Ronald J. Gould (1981)
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...
Jill R. Faudree, Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson, Colton Magnant (2010)
Discussiones Mathematicae Graph Theory
Similarity:
The Chvátal-Erdös theorems imply that if G is a graph of order n ≥ 3 with κ(G) ≥ α(G), then G is hamiltonian, and if κ(G) > α(G), then G is hamiltonian-connected. We generalize these results by replacing the connectivity and independence number conditions with a weaker minimum degree and independence number condition in the presence of sufficient connectivity. More specifically, it is noted that if G is a graph of order n and k ≥ 2 is a positive integer such that κ(G) ≥ k, δ(G) >...
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...
Z. Skupień (1989)
Banach Center Publications
Similarity:
Ladislav Nebeský (1980)
Mathematica Slovaca
Similarity:
Wong, Pak-Ken (1997)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Tudor Zamfirescu (1971)
Rendiconti del Seminario Matematico della Università di Padova
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.
Ján Ninčák (1974)
Commentationes Mathematicae Universitatis Carolinae
Similarity:
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...