			Home About us Contact

Hamiltonian Cycles (hamiltonian + cycle)

Distribution by Scientific Domains

Mathematics and Statistics	100%

Selected Abstracts

On the Hamiltonicity Gap and doubly stochastic matrices

RANDOM STRUCTURES AND ALGORITHMS, Issue 4 2009
Vivek S. Borkar
Abstract We consider the Hamiltonian cycle problem embedded in singularly perturbed (controlled) Markov chains. We also consider a functional on the space of stationary policies of the process that consists of the (1,1)-entry of the fundamental matrices of the Markov chains induced by these policies. We focus on the subset of these policies that induce doubly stochastic probability transition matrices which we refer to as the "doubly stochastic policies." We show that when the perturbation parameter, ,, is sufficiently small, the minimum of this functional over the space of the doubly stochastic policies is attained at a Hamiltonian cycle, provided that the graph is Hamiltonian. We also show that when the graph is non-Hamiltonian, the above minimum is strictly greater than that in a Hamiltonian case. We call the size of this difference the "Hamiltonicity Gap" and derive a conservative lower bound for this gap. Our results imply that the Hamiltonian cycle problem is equivalent to the problem of minimizing the variance of the first hitting time of the home node, over doubly stochastic policies. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009 [source]

Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets

JOURNAL OF GRAPH THEORY, Issue 2 2006
Rostislav Caha
Abstract This paper studies techniques of finding hamiltonian paths and cycles in hypercubes and dense sets of hypercubes. This problem is, in general, easily solvable but here the problem was modified by the requirement that a set of edges has to be used in such path or cycle. The main result of this paper says that for a given n, any sufficiently large hypercube contains a hamiltonian path or cycle with prescribed n edges just when the family of the edges satisfies certain natural necessary conditions. Analogous results are presented for dense sets. © 2005 Wiley Periodicals, Inc. J Graph Theory [source]

Edge-disjoint Hamiltonian cycles in hypertournaments

JOURNAL OF GRAPH THEORY, Issue 1 2006
Vojislav Petrovic
Abstract We introduce a method for reducing k -tournament problems, for k,,,3, to ordinary tournaments, that is, 2-tournaments. It is applied to show that a k -tournament on n,,,k,+,1,+,24d vertices (when k,,,4) or on n,,,30d,+,2 vertices (when k,=,3) has d edge-disjoint Hamiltonian cycles if and only if it is d -edge-connected. Ironically, this is proved by ordinary tournament arguments although it only holds for k,,,3. We also characterizatize the pancyclic k -tournaments, a problem posed by Gutin and Yeo.(Our characterization is slightly incomplete in that we prove it only for n large compared to k.). © 2005 Wiley Periodicals, Inc. J Graph Theory [source]

Independent dominating sets and hamiltonian cycles

JOURNAL OF GRAPH THEORY, Issue 3 2007
Penny Haxell
Abstract A graph is uniquely hamiltonian if it contains exactly one hamiltonian cycle. In this note we prove that there are no r -regular uniquely hamiltonian graphs when r,>,22. This improves upon earlier results of Thomassen. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 233,244, 2007 [source]

3-colorability of 4-regular hamiltonian graphs,

JOURNAL OF GRAPH THEORY, Issue 2 2003
Herbert Fleischner
Abstract On the model of the cycle-plus-triangles theorem, we consider the problem of 3-colorability of those 4-regular hamiltonian graphs for which the components of the edge-complement of a given hamiltonian cycle are non-selfcrossing cycles of constant length , 4. We show that this problem is NP-complete. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 125,140, 2003 [source]