DHCP & DNS

[zephod at cfl.rr.com]

I think my understanding is a little lacking on this subject (one of many).

Here is my simple and, I suspect, very common setup: 2 PCs, one FC6 Linux, one Windows Vista and a Linksys wireless router. A DHCP server on the Linksys determines the IP addresses of the 2 machines. 

My question is: is it possible for either machine to ping the other without having to make an entry in its local hosts file?  Making entries in the hosts file doesn't seem like a good idea since the IP address could, in theory, change.
The Linksys is a WRT54G and I don't think that it contains a DNS server. The names of my 2 machine should never get to a public DNS router since they are on a private network.

Steve