12 citations · 12 across the 2 of their papers we have counts for
6 papers
Adding random edges to create the square of a Hamilton cycle
Patrick Bennett, Andrzej Dudek, Alan Frieze
We consider how many random edges need to be added to a graph of order with minimum degree in order that it contains the square of a Hamilton cycle w.h.p..
On the number of alternating paths in bipartite complete graphs
Patrick Bennett, Andrzej Dudek, Elliot Laforge
Let be a code such that any two words of have Hamming distance at least . It is not difficult to see that determining a code with the maximum number…
Rainbow perfect matchings and Hamilton cycles in the random geometric graph
Deepak Bal, Patrick Bennett, Xavier Pérez-Giménez +1
Given a graph on vertices and an assignment of colours to the edges, a rainbow Hamilton cycle is a cycle of length visiting each vertex once and with pairwise different col…
Space proof complexity for random 3-CNFs
Patrick Bennett, Ilario Bonacina, Nicola Galesi +3
We investigate the space complexity of refuting -CNFs in Resolution and algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a random -CNF…
The t-tone chromatic number of random graphs
Deepak Bal, Patrick Bennett, Andrzej Dudek +1
A proper 2-tone -coloring of a graph is a labeling of the vertices with elements from such that adjacent vertices receive disjoint labels and vertices distance…
A greedy algorithm for finding a large 2-matching on a random cubic graph
Deepak Bal, Patrick Bennett, Tom Bohman +1
A 2-matching of a graph is a spanning subgraph with maximum degree two. The size of a 2-matching is the number of edges in and this is at least $n-\k(U)$ where is t…