There's a metric for OS Uptime that should get reset if the VM is restarted. If it is less than roughly 300 seconds (over a 5 minute collection interval) that should be a good indication that the VM was restarted. I say "roughly" 300 seconds because I've seen it be slightly higher than 300 after a VM was restarted. I assume this might be due to slight variances in collection times and the OS restarting very quickly. I would probably alert if it is under 600 seconds or more and allow the alarm to take two or more collection cycles to clear.
You might also be interested in this article that goes into detail about creating a super metric to monitor VM availability.
VM Availability Monitoring - virtual red dot
