Skip to main content
MathOverflow

Return to Answer

added 4 characters in body
Source Link
Gjergji Zaimi
Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402

The main aspect of the underlying graph of a random $m$-out graph (each vertex is given a random set of $m$ out-edges) that has been studied is the fact that they are a.s. Hamiltonian.

Denoting this graph by $D_m(n)$, it is known that $D_2$ almost surely contains a vertex adjacent to three vertices of degree two, and in the paper "On the existence of Hamiltonian cycles in a class of random graphs" Fenner and Frieze proved that $D_{23}$ is a.s. Hamiltonian. Finally Bohman and Frieze recently proved that $D_3$ is almost surely Hamiltonian in "Hamiltonian cycles in $3$-out""Hamiltonian cycles in $3$-out".

The main aspect of the underlying graph of a random $m$-out graph (each vertex is given a random set of $m$ out-edges) that has been studied is the fact that they are a.s. Hamiltonian.

Denoting this graph by $D_m(n)$, it is known that $D_2$ almost surely contains a vertex adjacent to three vertices of degree two, and in the paper "On the existence of Hamiltonian cycles in a class of random graphs" Fenner and Frieze proved that $D_{23}$ is a.s. Hamiltonian. Finally Bohman and Frieze recently proved that $D_3$ is almost surely Hamiltonian in "Hamiltonian cycles in $3$-out".

The main aspect of the underlying graph of a random $m$-out graph (each vertex is given a random set of $m$ out-edges) that has been studied is the fact that they are a.s. Hamiltonian.

Denoting this graph by $D_m(n)$, it is known that $D_2$ almost surely contains a vertex adjacent to three vertices of degree two, and in the paper "On the existence of Hamiltonian cycles in a class of random graphs" Fenner and Frieze proved that $D_{23}$ is a.s. Hamiltonian. Finally Bohman and Frieze recently proved that $D_3$ is almost surely Hamiltonian in "Hamiltonian cycles in $3$-out".

Source Link
Gjergji Zaimi
Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402

The main aspect of the underlying graph of a random $m$-out graph (each vertex is given a random set of $m$ out-edges) that has been studied is the fact that they are a.s. Hamiltonian.

Denoting this graph by $D_m(n)$, it is known that $D_2$ almost surely contains a vertex adjacent to three vertices of degree two, and in the paper "On the existence of Hamiltonian cycles in a class of random graphs" Fenner and Frieze proved that $D_{23}$ is a.s. Hamiltonian. Finally Bohman and Frieze recently proved that $D_3$ is almost surely Hamiltonian in "Hamiltonian cycles in $3$-out".