Bridges and Hamiltonian circuits in planar graphs.
W.T. Tutte (1977)
Aequationes mathematicae
Similarity:
W.T. Tutte (1977)
Aequationes mathematicae
Similarity:
Linda M. Lesniak (1978)
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...
C.ST.J.A. NASH-WILLIAMS (1971)
Aequationes mathematicae
Similarity:
Xiaoyun Lu, Douglas B. West (2016)
Discussiones Mathematicae Graph Theory
Similarity:
We prove a theorem guaranteeing special paths of faces in 2-connected plane graphs. As a corollary, we obtain a new proof of Thomassen’s theorem that every 4-connected planar graph is Hamiltonian-connected.
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...
Gary Chartrand, S. F. Kapoor (1974)
Colloquium Mathematicae
Similarity:
Magdalena Bojarska (2010)
Discussiones Mathematicae Graph Theory
Similarity:
We show that every 2-connected (2)-Halin graph is Hamiltonian.
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...
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.
Wong, Pak-Ken (1997)
International Journal of Mathematics and Mathematical Sciences
Similarity:
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.
Z. Skupień (1989)
Banach Center Publications
Similarity:
Ronald J. Gould (1981)
Colloquium Mathematicae
Similarity: