Hola despues de tu sentencia puedes poner esto:
Código PHP:
<?
if(mysql_affected_rows($cn))//$cn es la conexion
{
?>
<script language="javascript">
alert("Registro Eliminado Correctamente");
location.href="index.php";//aqui la pagina a donde vas a redirigir
</script>
<?
}
else
{
?>
<script language="javascript">
alert("Error al Eliminar");
setTimeout("url()",1000);
function url()
{
window.history.back();
}
</script>
<?
}
?>
Saludos.