Results 21 to 30 of about 60,523 (284)
The threshold for the square of a Hamilton cycle [PDF]
Proceedings of the American Mathematical Society, 2021 Resolving a conjecture of Kühn and Osthus from 2012, we show that p = 1 / n p= 1/\sqrt {n} is the threshold for the random graph G n , p G_{n,p} to contain the square of a Hamilton cycle.
Jeff Kahn +2 more
openaire +3 more sources
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
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
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
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
Hamilton cycles in quasirandom hypergraphs [PDF]
Random Structures & Algorithms, 2016 We show that, for a natural notion of quasirandomness in $k$-uniform hypergraphs, any quasirandom $k$-uniform hypergraph on $n$ vertices with constant edge density and minimum vertex degree $ (n^{k-1})$ contains a loose Hamilton cycle. We also give a construction to show that a $k$-uniform hypergraph satisfying these conditions need not contain a ...
Dhruv Mubayi, Richard Mycroft, John Lenz
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 +2 more sources
Discrepancies of spanning trees and Hamilton cycles [PDF]
Journal of Combinatorial Theory, Series B, 2022 We study the multicolour discrepancy of spanning trees and Hamilton cycles in graphs. As our main result, we show that under very mild conditions, the $r$-colour spanning-tree discrepancy of a graph $G$ is equal, up to a constant, to the minimum $s$ such that $G$ can be separated into $r$ equal parts by deleting $s$ vertices.
Lior Gishboliner +2 more
openaire +3 more sources
Packing Loose Hamilton Cycles [PDF]
Combinatorics, Probability and Computing, 2017 A subsetCof edges in ak-uniform hypergraphHis aloose Hamilton cycleifCcovers all the vertices ofHand there exists a cyclic ordering of these vertices such that the edges inCare segments of that order and such that every two consecutive edges share exactly one vertex.
Asaf Ferber +3 more
openaire +3 more sources
Directed Hamilton Cycles in Digraphs and Matching Alternating Hamilton Cycles in Bipartite Graphs [PDF]
SIAM Journal on Discrete Mathematics, 2013 16 pages, 7 figures, published on "Siam Journal on Discrete Mathematics"
Xuelian Wen, Xiaoyan Zhang, Zan-Bo Zhang
openaire +3 more sources