Results 181 to 190 of about 311 (214)
Some of the next articles are maybe not open access.
The Square of a Hamiltonian Cycle
SIAM Journal on Discrete Mathematics, 1994All graphs considered in this paper are simple and undirected. For a given graph \(G= (V,E)\) we denote by \(\delta(G)\) the minimum degree of \(G\). A \(k\)-chord of a cycle \(C\) is an edge joining two vertices of distance \(k\) on \(C\). The \(k\)th power of \(C\) is the graph obtained by joining every pair of vertices with distance at most \(k\) on
Genghua Fan, Roland Häggkvist
openaire +1 more source
A Remark on Hamiltonian Cycles
Mathematische Nachrichten, 1992AbstractLet G be an undirected and simple graph on n vertices. Let ω, α and χ denote the number of components, the independence number and the connectivity number of G. G is called a 1‐tough graph if ω(G – S) ⩽ |S| for any subset S of V(G) such that ω(G − S) > 1.
openaire +2 more sources
On Hamiltonian cycles in the FCC grid
Computers & Graphics, 2020Abstract The face centered cubic (FCC) grid is a space-filling grid, one of the alternatives to the traditional cubic one. We show that there are five Hamiltonian cycles (non-equivalent up to rotation and symmetry), connecting the faces of a voxel in the FCC grid.
Lidija Comic, Paola Magillo
openaire +2 more sources
A parallel reduction of Hamiltonian cycle to Hamiltonian Path in tournaments
Journal of Algorithms, 1993Summary: We propose a parallel algorithm which reduces the problem of computing Hamiltonian cycles in tournaments to the problem of computing Hamiltonian paths. The running time of our algorithm is \(O(\log n)\) using \(O(n^2/\log n)\) processors on a CRCW PRAM, and \(O(\log n \log \log n)\) on an EREW PRAM using \(O(n^2/ \log n \log \log n ...
Evripidis Bampis +3 more
openaire +1 more source
On Hamiltonian cycles as optimal p-cycles
IEEE Communications Letters, 2005Using Hamiltonian p-cycles, it can be shown that p-cycle design is able to reach the logical redundancy bound of 1/(d~-1) where d~ is the average node degree. We formulate two conditions on which the design is able to reach this bound if and only if Hamiltonian p-cycles are used.
openaire +1 more source
Hamiltonian Cycles and Tight Cutsets
Graphs and CombinatoricsLet \(G\) be a graph. A cutset \(S\) of \(G\) is tight if \(|S|=c(G-S)\). The authors define a reduction step in \(G\) to be the deletion of all edges joining two vertices that lie together in a tight cutset, making each tight cutset independent. The (Hamiltonian) reduction \(R(G)\) of a 1-tough graph \(G\) is the iterative application of reduction ...
Viswanathan B. N, Douglas B. West
openaire +2 more sources
Non‐Hamiltonian Cycles in Tournaments
Journal of Graph TheoryABSTRACTA cycle is said to be directed if all its arcs have the same direction. Otherwise, it is said to be nondirected. A strong tournament is a tournament containing a directed path from any vertex to any other vertex. A tournament that is not strong is said to be reducible.
openaire +2 more sources
Hamiltonian Cycles of Adjacent Triples
Studies in Applied Mathematics, 1980A construction is given for ordering triples chosen from an ordered set of elements, so that each triple agrees with each neighbor in two of its members and has third member that is a neighbor of its neighbor's third member. Neighbors here are adjacent in order, and also the first is neighbor to the last among both elements and triples.
openaire +1 more source
On the Number of Hamiltonian Cycles in a Tournament
Combinatorics, Probability and Computing, 2005It is shown that the maximum number \(C(n)\) of Hamiltonian cycles in a tournament of order \(n\) satisfies the inequaltiy \(C(n) < O(n^{3/2-\varepsilon}(n-1)!2^{-n})\), where \(\varepsilon = .2507\dots\). No claim is made concerning the sharpness of the bound.
Friedgut, Ehud, Kahn, Jeff
openaire +1 more source
Hamiltonian cycles in Dirac graphs
Combinatorica, 2009zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Bill Cuckler, Jeff Kahn 0001
openaire +2 more sources