Given a random graph which can be constructed as follows:

generate $s$ pairs of unconnected black edges and $2 \cdot s$ vertices

connect these black edges using red edges, where the average number of red edges on a vertex is $a$


What is the chance that, starting from a given vertex and following a random walk of alternating black and red edges that one doesn't end up with a Hamiltonian path in $n$ tries (in terms of $n$, $s$ and $a$). Or a good upperbound

Also is there a difference between this chance for a given $s$ and a graph with $s+k\text{ }$ black edges where one starts the walk with $k$ black edges already visited



a graph where $s = 3$ and $a = 2$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.