A fast roaming (handoff) service is provided for a WLAN infrastructure. A given mobile station (STA) obtains a pairwise master key (PMK) when it associates with an access point (AP) in the infrastructure. A neighbor graph identifies prospective APs to which the STA may then roam. At initialization, preferably the neighbor graph is fully-connected (i.e., each AP is assumed to be connected to every other AP). The PMK (obtained by the STA initially) is shared proactively with the neighbor APs as indicated in the neighbor graph. Thus, when the STA roams to a neighbor AP, because the PMK is already available, there is no requirement that the STA initiate a real-time request to an authentication server to re-associate to the new AP. Further, the new AP causes an update to the neighbor graph information implicitly by simply issuing a notification that it is now handling the STA that arrived from the prior AP; in this manner, the prior AP is confirmed as a neighbor, but there is no requirement for any inter-AP dialog before a given neighbor graph is updated. As roaming occurs the neighbor graph is pruned down (to reflect the actual neighbor AP connections) using the implicit notification data.