Results 191 to 200 of about 311 (214)

Disjoint Hamiltonian cycles in graphs [PDF]

Australas. J Comb., 1999
Let \(G\) be a \(2(k+1)\)-connected graph with the property \(uv \notin E(G)\) implies max\(\{ d(u),d(v) \} \geq n/2 + 2k\). It is shown that if \(\delta (G) \geq 4k+3\) then \(G\) contains \(k+1\) Hamiltonian cycles with no common edges. These cycles are constructed from the disjoint Hamiltonian cycles of a certain complete graph created from \(G ...
Guojun Li, Chuanping Chen
openaire   +1 more source

Some of the next articles are maybe not open access.

Related searches:

Hamiltonian cycles in delaunay complexes

1989
We restate a conjecture concerning the existence of Hamiltonian cycles in graphs resulting from the Delaunay triangulation of point sets in the plane R2. We introduce the notion of Delaunay complex, the natural completion of a Delaunay triangulation. We show that Delaunay complexes are necessarily 3-connected.
Henry Crapo, Jean-Paul Laumond
openaire   +1 more source

Hamiltonian Cycles in Regular Tournaments

Combinatorics, Probability and Computing, 2007
We show that every regular tournament on n vertices has at least n!/(2 + o(1)) n Hamiltonian cycles, thus answering a question of Thomassen [17] and providing a partial answer to a question of Friedgut and Kahn [7]. This compares to an upper bound of about O(n0.25n!/2 n ) for arbitrary tournaments due to Friedgut and Kahn ...
openaire   +1 more source

Hamiltonian cycles in bipartite graphs

Combinatorica, 1995
Let \(G= (X, Y; E)\) be a balanced bipartite graph with vertex classes \(X\), \(Y\), edge set \(E\), and \(|X|= |Y|= n\). The balanced independence number \(\alpha^*(G)\) is defined to be \[ \max\{|A|: A\subseteq X\cup Y\wedge A\text{ is independent }\wedge \bigl||A\cap X|- |A\cap Y|\bigr|\leq 1\}.
openaire   +2 more sources

Hamiltonian Cycles in Products of Graphs

Canadian Mathematical Bulletin, 1975
Let V(G) and E(G) denote the vertex set and the edge set of a graph G; let Kn denote the complete graph with n vertices and let Kn, m denote the complete bipartite graph on n and m vertices. A Hamiltonian cycle (Hamiltonian path, respectively) in a graph G is a cycle (path, respectively) in G that contains all the vertices of G.
openaire   +1 more source

Counting Hamiltonian cycles in planar triangulations

Journal of Combinatorial Theory Series B, 2022
Xingxing Yu, Zhiyu Wang, Xiaonan Liu
exaly  

Powers of Hamiltonian cycles in randomly augmented graphs

Random Structures and Algorithms, 2020
Andrzej Rucinski, Christian Reiher, Andrzej Dudek   +2 more
exaly  

Two edge-disjoint hamiltonian cycles in the butterfly graph

Information Processing Letters, 1994
André Raspaud, Dominique Barth
exaly  

Hamiltonian cycles in 4-connected plane triangulations with few 4-separators

Discrete Mathematics, 2020
On-Hei Solomon Lo
exaly  

Edge-disjoint Hamiltonian cycles of balanced hypercubes

Information Processing Letters, 2019
Huazhong Lu, Tingzeng Wu
exaly