I think scalability is really about having the ability to add capacity by adding components (hardware, typically) without any individual component becoming ever more loaded as system demand increases. In other words, in a scalable system there is no bottleneck component that will ultimately limit performance and throughput. Instead, performance and throughput ideally remain constant or at least shrink more slowly than demand on the system grows.
You are right to keep concepts like fault-tolerance and high-availability (and their implementation via replication) in mind, but I see them as more concerned with reliability than scalability. While often implemented together, they are two different things.
In your graph example, what is it that needs to scale?
Is it access to the graph (large numbers of simultaneous users)?
Regarding access, is it write access that needs to scale, or just read access?
Is it the size of the graph itself (e.g. large numbers of nodes like Facebook's social graph)?
What about complexity? Does each node need to support arbitrarily large numbers of connections?
Does each node (and therefore the system as a whole) need to hold arbitrarily large amounts of data?
These are some pragmatic issues that need to be addressed when one talks about scalability. Like most design challenges, it's really all about breaking the problem down into the core issues that need to be addressed.
Lastly, I see techniques like asynchronous programming as contributing to efficiency, but not scalability. Unless you are doing something major like replacing a quadratic algorithm with a linear one, efficiencies alone will not help much with scalability (see Amdahl's Law). They will help with the cost of scalability (a very pragmatic issue), but not with the potential for it.