A graph database is, literally, a database that handles graphs.
DB-Engines Ranking of Graph DBMS
A practical introduction for first-time graph database users
An overview of Apache TinkerPop