Results 1 to 10 of about 3,095,070 (339)
On Vertices Enforcing a Hamiltonian Cycle [PDF]
Discussiones Mathematicae Graph Theory, 2013 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.
Fabrici Igor +2 more
doaj +5 more sources
Complexity of Hamiltonian Cycle Reconfiguration [PDF]
Algorithms, 2018 The Hamiltonian cycle reconfiguration problem asks, given two Hamiltonian cycles C 0 and C t of a graph G, whether there is a sequence of Hamiltonian cycles C 0 , C 1 , … , C t such that C i can be obtained ...
Asahi Takaoka
doaj +3 more sources
Hamiltonian cycles in torical lattices [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 We establish sufficient conditions for a toric lattice $T_{m,n}$ to be Hamiltonian. Also, we give some asymptotics for the number of Hamiltonian cycles in $T_{m,n}$.
Vladimir K. Leontiev
doaj +5 more sources
Hamiltonian Cycles in Polyhedral Maps [PDF]
Proceedings - Mathematical Sciences, 2014 We present a necessary and sufficient condition for existence of a contractible, non-separating and noncontractible separating Hamiltonian cycle in the edge graph of polyhedral maps on surfaces.
Maity, Dipendu, Upadhyay, Ashish Kumar
core +4 more sources
Finding hidden hamiltonian cycles [PDF]
Random Structures & Algorithms, 1994 AbstractConsider a random graph G composed of a Hamiltonian cycle on n labeled vertices and dn random edges that “high” the cycle. Is it possible to unravel the structures, that is, to efficiently find a Himiltonian cycle in G? We describe an O(n3 log n)‐step algorithm A for this purpose, and prove that it succeeds almost surely. Part one of A properly
Andrei Broder, Alan Frieze, Eli Shamir
openalex +3 more sources
Oriented Hamiltonian Cycles in Tournaments
Journal of Combinatorial Theory, Series B, 2000 AbstractWe prove that every tournament of order n⩾68 contains every oriented Hamiltonian cycle except possibly the directed one when the tournament is reducible.
Frédéric Havet
openalex +4 more sources
Alternating Hamiltonian cycles in $2$-edge-colored multigraphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 A path (cycle) in a $2$-edge-colored multigraph is alternating if no two consecutive edges have the same color. The problem of determining the existence of alternating Hamiltonian paths and cycles in $2$-edge-colored multigraphs is an $\mathcal{NP ...
Alejandro Contreras-Balbuena +2 more
doaj +3 more sources
Ore-degree threshold for the square of a Hamiltonian cycle [PDF]
Discrete Mathematics & Theoretical Computer Science, 2014 A classic theorem of Dirac from 1952 states that every graph with minimum degree at least n/2 contains a Hamiltonian cycle. In 1963, P\'osa conjectured that every graph with minimum degree at least 2n/3 contains the square of a Hamiltonian cycle. In 1960,
DeBiasio, Louis +2 more
core +5 more sources
Extending a perfect matching to a Hamiltonian cycle [PDF]
Discrete Mathematics & Theoretical Computer Science, 2015 Graph ...
Adel Alahmadi +5 more
doaj +2 more sources
Parity balance of the $i$-th dimension edges in Hamiltonian cycles of the hypercube [PDF]
, 2010 Let $n\geq 2$ be an integer, and let $i\in\{0,...,n-1\}$. An $i$-th dimension edge in the $n$-dimensional hypercube $Q_n$ is an edge ${v_1}{v_2}$ such that $v_1,v_2$ differ just at their $i$-th entries.
Morales-Luna, Guillermo, Sagols, Feliú
core +3 more sources