Results 31 to 40 of about 3,567,425 (361)
Hamilton cycles in pseudorandom graphs
Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications, 2023 Finding general conditions which ensure that a graph is Hamiltonian is a central topic in graph theory. An old and well known conjecture in the area states that any $d$-regular $n$-vertex graph $G$ whose second largest eigenvalue in absolute value $\lambda(G)$ is at most $d/C$, for some universal constant $C>0$, has a Hamilton cycle.
Glock, Stefan +2 more
openaire +3 more sources
Multicoloured Hamilton Cycles [PDF]
The Electronic Journal of Combinatorics, 1995 The edges of the complete graph $K_n$ are coloured so that no colour appears more than $\lceil cn\rceil$ times, where $c < 1/32$ is a constant. We show that if $n$ is sufficiently large then there is a Hamiltonian cycle in which each edge is a different colour, thereby proving a 1986 conjecture of Hahn and Thomassen. We prove a similar result for
Alan Frieze +2 more
openaire +3 more sources
Loose Hamilton cycles in hypergraphs [PDF]
Discrete Mathematics, 2011 We prove that any k-uniform hypergraph on n vertices with minimum degree at least n/(2(k-1))+o(n) contains a loose Hamilton cycle. The proof strategy is similar to that used by K hn and Osthus for the 3-uniform case. Though some additional difficulties arise in the k-uniform case, our argument here is considerably simplified by applying the recent ...
Richard Mycroft +3 more
openaire +2 more sources
Oriented discrepancy of Hamilton cycles
Journal of Graph Theory, 2023 AbstractWe propose the following extension of Dirac's theorem: if is a graph with vertices and minimum degree , then in every orientation of there is a Hamilton cycle with at least edges oriented in the same direction. We prove an approximate version of this conjecture, showing that minimum degree guarantees a Hamilton cycle with at least edges ...
Lior Gishboliner +2 more
openaire +3 more sources
Finding a Hamilton cycle fast on average using rotations and extensions [PDF]
Random Struct. Algorithms, 2019 We present an algorithm CRE, which either finds a Hamilton cycle in a graph G or determines that there is no such cycle in the graph. The algorithm's expected running time over input distribution G∼G(n,p) is (1+o(1))n/p, the optimal possible expected ...
Yahav Alon, Michael Krivelevich
semanticscholar +1 more source
Resilience for loose Hamilton cycles
Procedia Computer Science, 2023 We study the emergence of loose Hamilton cycles in subgraphs of random hypergraphs. Our main result states that the minimum $d$-degree threshold for loose Hamiltonicity relative to the random $k$-uniform hypergraph $H_k(n,p)$ coincides with its dense analogue whenever $p \geq n^{- (k-1)/2+o(1)}$.
Alvarado, José D. +4 more
openaire +2 more sources
Finding Hamilton cycles in random intersection graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 The construction of the random intersection graph model is based on a random family of sets. Such structures, which are derived from intersections of sets, appear in a natural manner in many applications. In this article we study the problem of finding a
Katarzyna Rybarczyk
doaj +1 more source
Identifying Hamilton cycles in the Cartesian product of directed cycles
AKCE International Journal of Graphs and Combinatorics, 2020 Let be a Cartesian product of directed cycles. It is known that has a Hamilton cycle if there is a permutation of that satisfies and for some positive integers , where . In addition, if then has two arc-disjoint Hamilton cycles.
Zbigniew R. Bogdanowicz
doaj +1 more source
On Implicit Heavy Subgraphs and Hamiltonicity of 2-Connected Graphs
Discussiones Mathematicae Graph Theory, 2021 A graph G of order n is implicit claw-heavy if in every induced copy of K1,3 in G there are two non-adjacent vertices with sum of their implicit degrees at least n. We study various implicit degree conditions (including, but not limiting to, Ore- and Fan-
Zheng Wei, Wideł Wojciech, Wang Ligong
doaj +1 more source
Well-spread sequences and edge-labellings with constant Hamilton-weight [PDF]
Discrete Mathematics & Theoretical Computer Science, 2004 A sequence (a_i) of integers is \emphwell-spread if the sums a_i+a_j, for ...
Peter Mark Kayll
doaj +1 more source