I assume you are aware that the vertex-transitive graphs represent a relatively constrained list? See [this description][1]. I fear that adding your conditions (2,3,4) on top of vertex-transitivity will again confine you to the skeletons of the Platonic solids. Are you familiar with Fuller's [geodesic domes][2]? They fail to satisfy your criteria, but they get perhaps as close as is feasible, and may serve, depending upon your application: <br /> ![Geodesic Dome][3] <br /> <hr> After seeing your addendum on motivation, perhaps you should investigate the literature on packing disks on a sphere. For example, you might explore Neil Sloane's web pages on "[Nice arrangements of points on a sphere in various dimensions][4]" which address the problem of > placing $n$ points on a sphere in $d$ dimensions so as to maximize the minimal distance (or equivalently the minimal angle) between them. For example, here is the best packing known for $n=50$, due to Székely (1974): <br /> ![50 points on sphere][5] <br /> <sub>[Image © Hugo Pfoertner, 2001][6]</sub> [1]: http://en.wikipedia.org/wiki/Vertex-transitive_graph#Finite_examples [2]: http://mathworld.wolfram.com/GeodesicDome.html [3]: https://i.sstatic.net/fEsSg.jpg [4]: http://www2.research.att.com/~njas/packings/ [5]: https://i.sstatic.net/uZ5em.jpg [6]: http://www.enginemonitoring.org/sphere/index_4.htm