hola, utilizas css?
si es asi podes hacer lo siguiente:
<div id="botmenu">
<ul>
<li><a href="#" rel="nofollow">inicio</a></li>
<li><a href="#" rel="nofollow">Historia</a></li>
<li><a href="#" rel="nofollow">Contactanos</a></li>
</ul>
</div>
en el css:
#botmenu
{
}
#botmenu li
{
}
#botmenu li a
{
border-bottom:none;
}
#botmenu li a:hover
{
border-bottom:red;
}
si no entiendes algo me avisas