  In the private information retrieval (PIR) problem, a user wants to retrieve
a file from a database without revealing any information about the desired
file's identity to the servers that store the database. In this paper, we study
the PIR capacity of a graph-based replication system, in which each file is
stored on two distinct servers according to an underlying graph. This paper
aims to provide upper and lower bounds to the PIR capacity of graphs via
various graph properties. In particular, we provide several upper bounds on the
PIR capacity that apply to all graphs. We further improve the bounds for
specific graph families (which turn out to be tight in certain cases) by
utilizing the underlying graph structure. For the lower bounds, we establish
optimal rate PIR retrieval schemes for star graphs via edge-coloring
techniques. Lastly, we provide an improved PIR scheme for complete graphs,
which implies an improved general lower bound on all graphs' PIR capacity.
