How can you determine the hostname associated with an IP on the network?
The zeroconf protocol suite (Wikipedia) could provide this information.
The best known implementations are AllJoyn (Windows and others), Bonjour (Apple), Avahi (UNIX/Linux).
Example showing a list of everything on a LAN (in this case not very much):
avahi-browse --all --terminate
+ ens18 IPv6 Canon MG6650 _privet._tcp local
+ ens18 IPv4 Canon MG6650 _privet._tcp local
+ ens18 IPv6 Canon MG6650 Internet Printer local
+ ens18 IPv4 Canon MG6650 Internet Printer local
+ ens18 IPv6 Canon MG6650 UNIX Printer local
+ ens18 IPv4 Canon MG6650 UNIX Printer local
+ ens18 IPv6 Canon MG6650 _scanner._tcp local
+ ens18 IPv4 Canon MG6650 _scanner._tcp local
+ ens18 IPv6 Canon MG6650 _canon-bjnp1._tcp local
+ ens18 IPv4 Canon MG6650 _canon-bjnp1._tcp local
+ ens18 IPv6 Canon MG6650 Web Site local
+ ens18 IPv4 Canon MG6650 Web Site local
+ ens18 IPv6 SERVER _device-info._tcp local
+ ens18 IPv4 SERVER _device-info._tcp local
+ ens18 IPv6 SERVER Microsoft Windows Network local
+ ens18 IPv4 SERVER Microsoft Windows Network local
More specifically, you can use avahi-resolve-address
to resolve an address to a name.
Example
avahi-resolve-address 192.168.1.254
192.168.1.254 router.roaima...